为下面的谜题提出一个算法!

Question

有n个汽油铺位在圆圈中.每个铺位与其余铺位隔开一定距离.你选择一些需要1升汽油才能覆盖1公里距离的旅行方式.你不能从每个铺位无限地抽取任何数量的汽油,因为每个铺位只有一些有限的汽油.但是你知道所有铺位中汽油升的总和等于要覆盖的距离.

即让P1,P2,...... Pn为圆形排列的n个铺位.d1是p1和p2之间的距离,d2是p2和p3之间的距离.dn是pn和p1之间的距离.现在找出可以开始旅行的铺位,这样你的旅行方式永远不会耗尽燃料.

Answer 1

让我们选择一个我们知道是错误的垃圾算法来看看它为什么是错误的......

符号...

当前点：（当前点的加仑气体，到达下一个点所需的加仑数）-> 剩余气体（加仑）

用更数学的形式来说：

P[i]: (g(P[i]), d(P[i+1])) -> 来自 i= 的 (g(P[i]) - d(P[i+1])) 之和1 到当前点-1

（现在来说说糟糕的算法......）

P1: (2,2) -> 0 (at P2)
P2: (5,3) -> 2 (at P3)
P3: (2,4) -> 0 (at P4)
P4: (2,5) -> -3 (ran out of gas 3 miles short of P5)

为了达到 P5，我们必须在达到 P3 时额外拥有 3 加仑汽油，为了在 P3 时拥有额外 3 加仑汽油，我们需要在 P1 时拥有额外 3 加仑汽油：

??? -> +3 (at P1)
P1: (2,2) -> 0+3 = 3 (at P2)
P2: (5,3) -> 2+3 = 5 (at P3)
P3: (2,4) -> 0+3 = 3 (at P4)
P4: (2,5) -> -3 +3 = 0 (made it to P5)

因此，诀窍是找到最糟糕的部分——在那里你没有足够的气体来穿越它们。我们知道我们不能从 P4、P3、P2 或 P1 开始。我们必须早点从某个地方开始，并储存足够的汽油才能通过糟糕的路段。

毫无疑问，圆圈内会有多个坏部分，这使得事情变得有些复杂，但实际上很容易弄清楚如何做到这一点。

绕圈中最糟糕的一段路段之后的接下来的几个点可能会在这段路段结束后行驶，但前提是它们不会改变您的气体储备。（例如，最糟糕的拉伸之后的点会为您提供 2 加仑的汽油，并让您行驶 2 加仑的距离到达下一个点。）

然而，在某些情况下，最差的部分必须最后覆盖。这是因为在开始该部分之前，您需要尽可能多地节省气体，而最糟糕的拉伸之后的下一个点可能会为您提供所需的最后一点气体，这意味着您需要在采取之前穿过它在最糟糕的情况下。尽管可能存在多种解决方案，但问题的简单事实是，最后遍历最差的部分始终是一个解决方案。这是一些代码：

class point_ {
int gasGiven_;
int distanceToNextPoint_;

public:
int gasGiven() {return gasGiven_;}
int distanceToNextPoint {return distanceToNextPoint_;}
}

class Circle_ {
public:
numberOfPoints;
point_ *P;
}

在主函数（）中：

int indexWorstSection=0;
int numberPointsWorstSection=0;
int worstSum=0;
int currentSum=0;
int i=0; 
int startingPoint =0;

// construct the circle, set *P to malloc of numberOfPoints point_'s, fill in all data

while (i<(Circle.numberOfPoints-1) || currentSum<0)
   {
   currentSum += Circle.P[i].gasGiven() - Circle.P[i].distanceToNextPoint();

   if (currentSum < worstSum) { worstSum = currentSum; indexWorstSection=i-numberPointsWorstSection; startingPoint=i;}

   if (currentSum>0) { currentSum=0; } 
     else { numberPointsWorstSection++; }

   if (i==(Circle.numberOfPoints-1)) { i=0; }
     else { i++; }
   }

if (indexWorstSection<0) indexWorstSection=Circle.numberOfPoints+indexWorstSection;

不能将其设为 for 循环的原因是因为最糟糕的部分可能是，例如，从 i=(Circle.numberOfPoints -2) 到 i=3。如果 currentSum 小于零，则必须继续回到数组的开头。

近十年来没有尝试过这些代码，也没有进行过任何认真的编程。抱歉，如果有一些错误。毫无疑问，您必须稍微清理一下。