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