是的，O（n）是可能的。绝对不是TSP。

令x i是第i站的可用天然气量减去前往下一个站所需的天然气量。

要求是ΣX 我 ≥0（足够的气体以完成一整圈）。

考虑S i = x 1 + x 2 + … + x i

注意，S ñ ≥0。

现在选择最小的（或什至最大的），从而使k最小，并从其旁边的站开始，从而更容易为k编写代码。

现在对于k <Ĵ≤N，我们有气体在罐= S Ĵ - S ķ ≥0。

1个≤Ĵ≤K，我们有气体在罐= X K + 1 + … + X Ñ + X 1 + X 2 + … + X Ĵ = S ñ - S ķ
+ S Ĵ ≥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;
}