卡车绕一圈加油站移动的算法

Question

您有一辆卡车绕着圆形轨道行驶，加油站围绕圆圈分布。每个加油站的汽油量都是有限的。卡车上的油箱无限大。加油站之间的距离需要一定量的汽油才能穿越。你只能朝一个方向移动。

使用什么算法？你从哪个加油站开始？你能一路绕到起点站吗？

Answer 1

是的 O(n) 是可能的。绝对不是 TSP。

令 x_i 为第 i 站可用的 gas 量减去下一站所需的 gas 量。

要求是 Σ x_i ≥ 0(足够的气体来完成一个完整的圆圈)。

考虑 S_i = x₁ + x₂ + ... + x_i

请注意 S_n ≥ 0。

现在选择最小的(甚至最大的都可以，这样更容易编写代码)k 使得 S_k 最小，并从它旁边的车站开始。

现在对于 k < j ≤ n，我们有 jar 中的气体 = S_j - S_k ≥ 0。

对于 1 ≤ j ≤ k，我们在 jar 中有气体 = x_k+1 + .. + x_n + x₁ + x₂ + .. + x_j = S_n - S_k + S_j ≥ 0.

因此从 k+1 开始将确保每个站点都积累了足够的气体以到达下一站点。

// 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;
}