为以下难题提出一个算法！

Question

有 n 个汽油铺位，排列成圆圈。每个铺位与其他铺位之间有一定的距离。您选择某种需要 1 升汽油才能行驶 1 公里距离的旅行方式。您不能无限地从每个铺位抽取任意数量的汽油，因为每个铺位只有一些有限的汽油。但您知道所有铺位中的汽油升数总和等于要行驶的距离。

即令P1、P2、...Pn 为循环排列的n 个铺位。 d1是p1和p2之间的距离，d2是p2和p3之间的距离。 dn 是 pn 和 p1 之间的距离。现在找出可以开始旅行的铺位，这样您的旅行方式就不会耗尽燃料。

Answer 1

有一个 O(n) 算法。

假设 v[0] = p1 - d1，v[1] = p2 - d2，...，v[n-1] = pn - dn。我们需要做的就是找到一个起点i，使得所有部分和不小于0，即v[i] >= 0，v[i] + v[(i+1)%n] >= 0, v[i] + v[(i+1)%n] + v[(i+2)%n] >= 0, ..., v[i]+...+v [(i+n-1)%n] >= 0。

我们可以通过计算 s[0] = v[0], s[1] = v[0]+v[1] 找到这样一个起点， s[2] = v[0]+v[1]+v[2], ..., s[n-1] = v[0] + ... + v[n-1]，然后拾取最小 s[k]。那么索引(k+1)%n就是起点。

证明：假设最小元素为s[k]。根据问题描述，必然存在最小值 s[k] <= 0。

因为总和 v[0] + v[1] + ... + v[n-1] = 0，所以有 v[ k+1] + v[k+2] + ... v[n-1] = -s[k] >= 0，不可能 v[k+1] + ... v[j ] < 0(k＜j＜n)。 （因为如果 v[k+1] + ... v[j] < 0，则 s[j] < s[k]，这与 s[k] 最小的假设相矛盾。）所以我们有 v[k+1] >= 0、v[k+1] + v[k+2] >= 0、...、v[k+1] + v[k+2] + .. . + v[n-1] >= 0。

因为 s[k] 是最小的，所以我们还有 v[k+1] + v[k+2] + ... + v[n-1] + v[0] = -s[k] + v[0] = -s[k] + s[0] >= 0, -s[k] + v[0] + v[1] = -s [k] + s[1] >= 0, ..., -s[k] + v[0] + v[1] + ... + v[k-1] = -s[k] + s[k-1]>=0。因此从(k+1)开始的所有部分和不小于0。QED。

Answer 2

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

符号...

当前点：（当前点的加仑气体，产生下一个点所需的加仑）->;剩余气体（加仑）

采用更数学化的形式：

P[i]: (g(P[i]), d(P[i+1])) ->从 i=1 到当前点-1 的 (g(P[i]) - d(P[i+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;
}

在 main() 中：

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 小于零，则它必须继续返回到数组的开头。

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

Answer 3

这与其他几个答案的作用相同 - 找到当您绕行时由汽油净变化三角洲创建的“图表”的最小值。根据我们开始的位置，与其他起始位置相比，确切的值可能会统一向上或向下移动，但最小值的索引始终是我们可以从哪里开始的有意义的指示，并且知道我们永远不会用完汽油。此实现尝试最小化内存使用并在 O(n) 内完成。

#include <iostream>

int dist[] = { 3, 10, 2, 4, 6, 9 };
int refill[] = { 3, 4, 6, 3, 7, 11 };

static const int n = sizeof dist / sizeof *dist;

int main()
{
    int cum = 0, min = 0, min_index = 0;
    for (int i = 0; i < n; ++i)
    {
        cum += refill[i] - dist[i];
        std::cout << cum << ' ';
        if (cum <= min)
        {
            min = cum;
            min_index = i;
        }
    }
    std::cout << "\nstart from index " << (min_index + 1) % n << " (0-based)\n";
}

查看它在 ideone.com 上运行的情况

Answer 4

这是一种适用于 O(n) 时间和 O(1) 空间的方法。从任意站点开始，将其称为站点 0，然后前进，直到耗尽汽油。如果你没有耗尽汽油，就完成了。否则，如果您在 k 站和 k+1 站之间用完，请在 k+1 站重新开始。如果再次传递0，请记下，如果之后用完则无法完成。

这样做的原因是，如果您从站 i 出发，并在站 k 和 k+1 之间用完汽油，那么您也会如果您从 i 和 k 之间的任何车站出发，则在 k+1 车站之前汽油耗尽。

这是一个算法，给定数组 P（汽油）和 D（距离）：

int position = 0;
int petrol = P[0];
int distance = D[0];

int start = 0;
while (start < n) {
    while (petrol >= distance) {
        petrol += P[++position % N] - distance;
        distance = D[position % N];
        if (position % N == start)
            return start;
    }
    start = position;
    petrol = P[start];
}
return -1;

Answer 5

每一段旅程都会对燃料产生净影响，燃料会从储存中添加并用于完成旅程。您所需要做的就是循环一次，在到达每个点时跟踪您的燃油水平，即使它是负值。跟踪最低燃油位及其发生位置。如果你从那个点开始，你将能够从那里开始，而不会耗尽燃料。这假设你从一个空的油箱开始，只能从你开始的地方获得汽油，而且你总是可以拿走所有的汽油，你永远不会充满并且不得不留下汽油。

假设您有 5 个积分，从 P1 到 P5：

Point  Fuel  Distance to next point
P1     5     8
P2     3     4
P3     12    7
P4     1     4
P5     7     5

如果您选择 P1，则加载 5 燃料，前往 P2 时您将剩下 -3 燃料。继续下去，你会得到这些数字：

Point  Fuel Balance (before refueling)
P1     0
P2     -3
P3     -4
P4     1
P5     -2
P1     0

所以，如果你从最低值 P3 开始，你可以让它回来（开始时加油 0，P4 加油 5，P5 加油 2，P1 加油 4，P2 加油 1，P3 加油 0） ）

float [] storedFuel = { 1, 1, 1, 1, 1, 1 };
float [] distance = { 1, 1, 1, 1, 1, 1 };
int n = 6;

int FindMinimumPosition()
{
    float fuel = 1;
    int position = 0;
    float minimumFuel = 1;
    int minimumPosition = 0;

    while (position < n)
    {
        fuel += storedFuel[position];
        fuel -= distance[position];
        position++; // could be n which is past array bounds
        if (fuel < minimumFuel) {
            minimumFuel = fuel;
            minimumPosition = position % n;
        }
    }

    return minimumPosition
}

Answer 6

在我的脑海中，这是一个应该有效的算法：

1. 令 e1 =（P1 中的汽油量）- d1（即，P1 中的汽油超出了前往 P2 所需的汽油量），对于 e2 也类似， ...，en。 （这些数字可以是正数或负数。）
2. 形成部分和 s1 = e1； s2 = e1 + e2； ..., sn = e1 + e2 + ... + en。从问题的条件我们知道 sn = 0。

现在的问题是找到床铺（或者更简单地说，e 值）的循环排列，使得 s 值都不为负。人们可以简单地重复移动 1，更新 s 值，直到找到解决方案。 （总有解决方案并不是很明显，但我认为是有的。如果你移动 n 次而没有找到解决方案，那么你保证没有解决方案。）

这是一个 O(n^2) 算法 - -不太好。一个好的启发式（可能是精确的解决方案）可能是进行移动，以便将最大幅度的负 s 值移动到位置 n。

Answer 7

对于每个缺口，求出在缺口之前的铺位填满，然后跨越缺口所赚取的利润或损失。在任意点计算出完整圆的每个点剩余的汽油总量，接受在某个点可能为负值。

现在反复循环移动该解决方案。删除最后一点的信息，该点现在将成为第一个点。设置偏移量以考虑到您现在开始向后移动一个点，并且在每个剩余点将增加（或减少）汽油。考虑偏移量，添加新点的信息。如果任意点的最小汽油量加上偏移量大于零，则该解决方案是可行的。

您可以使用某种 log n 数据结构（排序映射、优先级队列...）来跟踪最小值，以便将成本降至 n log n。

Answer 8

这是一个 O(n) 解决方案

private int findStartingPoint(int[] petrol, int[] dist, int[] mileage){
    int curPoint = 0;
    boolean done = false;
    while(curPoint < petrol.length && !done)
    {
        int prevPoint = curPoint;
        int nextPoint = (curPoint+1) % petrol.length;
        int nextSolutionPoint = curPoint + 1;
        int totalPetrol = 0;
        while(nextPoint != curPoint){
            totalPetrol += petrol[prevPoint] - (dist[prevPoint]/mileage[prevPoint]);
            if(totalPetrol < 0){
                curPoint = nextSolutionPoint;
                break;
            }
            prevPoint = nextPoint;
            nextPoint = (nextPoint + 1) % petrol.length;
            nextSolutionPoint++;
        }
        if(curPoint == nextPoint){
            return curPoint;
        }
    }
    return -1;
}

}