Description

在一条环路上有 \(n\) 个加油站,其中第 \(i\) 个加油站有汽油 \(gas[i]\) 升。

你有一辆油箱容量无限的的汽车,从第 \(i\) 个加油站开往第 \(i+1\) 个加油站需要消耗汽油 \(cost[i]\) 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 \(gas\) 和 \(cost\) ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 \(-1\) 。如果存在解,则 保证 它是 唯一 的。

Constraints

  • \(1 \le n \le 10^5\)
  • \(0 \le gas[i], cost[i] \le 10^4\)

Solution

一开始我是想着推式子的,可惜不会

另一个想法是贪心:如果从\(i\)出发,最多只能到\(j\)。那么换成从\([i+1, j-1]\)任意点出发更不可能到达\(j\)。因此下一次再从\(j\)开始遍历即可

Code

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        if(n == 1) return gas[0] >= cost[0] ? 0 : -1;
        int from = 0;
        for(;;) {
            int sumCost{}, sumGas{};
            int to = from;
            for(int i = from; i < from + n; ++i) {
                int realIndex = i % n;
                sumGas += gas[realIndex];
                sumCost += cost[realIndex];
                if(sumCost > sumGas) {
                    break;
                }
                to = i;
            }
            if(to > 2 * n) return -1;
            if(abs(to - from) == n-1) {
                return from;
            }
            if(to == from) to++;
            from = to;
        }
    }
};

LeetCode-134 Gas Station