问汽车在加油站圆圈内移动的算法

EN

这是一种在O(n)时间和O(1)空间中工作的方法(与Aryabhatta的答案中的O(n)空间相反)。

从任何一个加油站开始，称它为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;

假设cost是到下一个加油站的费用数组，gas是我们可以补充多少燃料的数组

我们计算gas[i]和cost[i]之间的差值，称为diff，其中i是我们当前所在的加油站。

如果是cost[i] > gas[i] (或diff < 0)，这意味着我们在到达i站时至少需要有cost[i] - gas[i]燃料才能到达下一站i+ 1。如果是cost[i] <= gas[i] (diff >= 0)，这是一个有效的起点，因为我们可以在没有汽油的情况下出发，加满油，然后前往下一站。在最坏的情况下，我们会带着一个空的油箱到达下一站。在最好的情况下，当我们到达i+1 (diff > 0)时，我们会有额外的燃料

我们实际上不必从一个加油站出发，成功地遍历n个加油站，看看是否有有效的旅行！只要总和油费>=总和，就会有一个有效的巡视。因此，我们只需要对数组执行O(n)遍操作

更多分析：

Case1:坦克降至0以下

这只会发生在diff < 0。可能会有另一个起点，在经过这个车站一圈后收集足够的多余燃料。但是，我们以前经过的所有站点都没有帮助，所以我们不需要考虑它们(参见案例2的解释)。

案例2: Tank当前为>=0，但我们遇到另一个有效的起点

我们可以放心地忽略这一点，因为：

A--B-- C。如果B可以到达C，A可以到达B，那么A可以到达C。

案例3: Tank当前为>=0，不是有效的起点

继续进行到下一个

案例4:设法到达最初的起点！

耶！

def find_starting_station(gas, cost):
    sum_gas = sum_cost = tank = start = 0

    for i in range(0, len(gas)):
        sum_gas += gas[i]
        sum_cost += cost[i]
        tank += gas[i] - cost[i]

        if tank < 0:
            tank = 0
            start = i+1

    if sum_gas < sum_cost: 
        return -1 

    return start

这个问题的解决方案是基于贪心算法。它基于以下两个观察结果。

1. 如果总耗油量>成本，则必须有一个起始索引才能结束循环，否则就没有了；

对于一个索引i，如果 i，j是我们不能到达的第一个索引，那么从i到j的任何一个索引都不能是起始索引。

有关更多解释，请查看以下链接- Gas Station problem.