8.19 gasStation

• 暴力法 timeout
• better

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = cost.size(), sum;
        for (int start=0; start<n;) {
            if (gas[start]-cost[start] < 0) {
                ++start;
                continue;
            } 
            sum = 0;
            int j=start;
            for (; j<start+n; ++j) {
              sum += gas[j%n]-cost[j%n];
              if (sum<0) break;
            }
            if (j==start+n) return start;
            else start = j;
        }
        return -1;//should never be
    }

诶居然想这么久，想到要把gas[i]-cost[i]，而且正确的starti此数不能是负的。然而没考虑好然后怎么才能从O（n^2）回到O（n）。

• We are looking for if we can find a starti that allows us to traverse without ever getting negative gas total, meaning we can safely get to any gas station starting from here.
• ~Given if there's solution it must be unique, there's only one starti that can reach all other stations while other stations can not safely reach starti.~ (can used this property to eliminate answer)
• So if we start at some index tryi, and end up out of gas at index tryi+m: we know tryi and tryi+m cannot be the answer. Moreover, any index in between cannot be neither. (cuz of property above)