There are n gas stations along a circular route, where the amount of gas at the \(i\)th station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the \(i\)th station to its next \((i + 1)\)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return \(-1\). If there exists a solution, it is guaranteed to be unique

Solution

给定一个圆环，有若干个加油站，问是否存在一个起始点使得空油箱的汽车跑完一周。不妨记：

假设从 \(i\) 开始，此时到达 \(i+1\) 需要满足：

类似地，到达 \(i+2\) 需要满足：

可以发现这就是前缀和，对于环形问题，我们可以摊开为一个 \(2n\) 的序列即可。所以只需要所有的前缀和非负即可

class Solution {
private:
    int dif[200005];
    int ans = 0;
    
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int ck = 0;
        for(int i=0;i<n;i++)dif[i] = gas[i]-cost[i], ck += dif[i];
        for(int i=n;i<2*n;i++)dif[i] = dif[i-n];
        int fg=0;
        if(ck<0)return -1;
        
        int tank_V = 0, st = 0;
        for(int i=0;i<2*n;i++){
            tank_V += dif[i];
            if(tank_V<0){
                tank_V = 0;
                st = i+1;
            }
        }
        return st%n;
    }
};