您有一辆卡车的圆形轨道与加油站四处移动隔开绕了一圈。每个站都有气体的量有限。在卡车的油箱是无限大的。加油站之间的距离需要一定量的气体来遍历的。您只能朝一个方向发展。

You have a truck moving around a circular track with gas stations spaced out around the circle. Each station has a finite amount of gas. The gas tank on the truck is infinitely big. The distance between the gas stations requires a certain amount of gas to traverse. You can only move in one direction.

什么是要使用的算法？ 你在哪启动加油站？ 让您可以和后面一路起始桩号？

What is the algorithm to use? Which gas station do you start at? Can you get all the way around and back to the start station?

推荐答案

是O（n）是可能的。非也TSP。

Yes O(n) is possible. Definitely not TSP.

设x 我是气体可在车站的金额我减去气体进入下一个工位所需的时间。

Let xi be the amount of gas available at station i minus the amount of gas required to go to next station.

一个要求是：西格玛; x 我＆GE; 0（足够的天然气来完成一个完整的圆）。

A requirement is Σ xi ≥ 0 (enough gas to complete a full circle).

考虑小号我 = X 1 + X 2 + ... + X 我

Consider Si = x1 + x2 + ... + xi

注意，S N ＆GE; 0。

Note that Sn ≥ 0.

现在挑最小的（甚至是最大的都会做，使它更易于编写$ C $下）K使得S K 是最少的，并开始在车站旁边。

Now pick the smallest (or even largest will do, making it easier to write code for) k such that Sk is the least and start at the station next to it.

现在的K＆LT; J＆乐; N，我们有气体罐= ​​S Ĵ - S K ＆GE; 0。

Now for k < j ≤ n, we have the gas in tank = Sj - Sk ≥ 0.

1＆乐; J＆乐; K，我们有天然气罐= X K + 1 + ... + X N + X 1 + X 2 + ... + X Ĵ = S N - S K + S Ĵ＆GE; 0。

for 1 ≤ j ≤ k, we have gas in tank = xk+1 + .. + xn + x1 + x2 + .. + xj = Sn - Sk + Sj ≥ 0.

因此​​，日K开始+ 1将确保有各站积累了足够的气才能到下一个站。

Thus starting at k+1 will ensure there is enough gas accumulated at each station to get to the next station.

// C++ code. gas[i] is the gas at station i, cost[i] is the cost from station i to (i+1)%n
int circ(vector<int> &gas, vector<int> &cost) {
    int min_S=INT_MAX, S=0, position=0;
    for(int i=0;i<gas.size();i++)
    {
        S += gas[i] - cost[i];
        if(S<min_S)
        {
            min_S = S;
            position = (i+1) % gas.size();
        }
    }
    if(S>=0)
        return position;
    else
        return -1;
}