佛山网站建设no.1定制网站建设

根据题解
这道题使用贪心算法，找到当前可解决问题的状态即可

「贪心算法」的问题需要满足的条件：

1. 最优子结构：规模较大的问题的解由规模较小的子问题的解组成，规模较大的问题的解只由其中一个规模较小的子问题的解决定；
2. 无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
3. 贪心选择性质：从局部最优解可以得到全局最优解。

如果要求走一圈，则总剩余油量total应该大于等于0
而在每个站点的时候，当前剩余油量curr如果大于等于0，代表可以到达下一个站点，如果小于0，代表从当前及之前的站点出发无法到达下一个站点，于是出发点改为下一个站点。
为什么说当前及之前的站点出发都无法到达下一个站点呢？
参考这个题解的图：

可以看到，假设start已经更改为3之后，可以到达4，假设到下一个节点时，cursum变成了负数，而在这之前的两个站点的cursum都是正数，代表它俩的加和都不够，更别提其中一个了 ，所以start会跳过4，更新为i+1。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();int start = 0;int curr = 0;int total = 0;for (int i = 0; i < n; ++i) {curr += gas[i] - cost[i];total += gas[i] - cost[i];if (curr < 0) {start = i + 1;curr = 0;}}return total >= 0 ? start : -1;}
};