EEPW论坛

There are N gas stations along a circular route, where the amount of gas at station i isgas[i].

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

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note: 

The solution is guaranteed to be unique.

题意：
环形路线上有N个加油站，每个加油站有汽油gas[i],从每个加油站到下一站消耗汽油cost[i]
问从哪个加油站出发能够回到起始点，如果都不能则返回-1；注意,解释唯一的；

思路：
累加在每个位置的left += gas[i]-cost[i].就是在每个位置剩余的油量，如果left一直大于0，
则可一直走下去，如果left小于0,那么就从下一个位置重新开始计数，并且将之前欠下的多少记录下来，
如果最终遍历完数组剩下的燃料足以弥补之前不够的，那么就可以到达，并返回最后一次开始的位置，否则返回-1；


论证这种方法的正确性：
1，如果从头开始，每次累计剩下的油量都为整数，那么没有问题，它可以从头开到结束
2. 如果到中间的某个位置，剩余的油量为负了，那么说明之前积累下来的油量不够从这一战
到下一站，那么就从下一站从新开始计数，为什么从下一站，而不是从之前的谋战呢？
因为第一站剩余的油量肯定大于等于0的，然而到当前油量变负了，说明从第一站之后开始的话当前油量只会更少
不会怎加，也就说从第一站之后，当前站之前的某站出发到当前站之前的某站出发到当前站出发的剩余
的油量是不大可能大于0的，所以只能从下一站重新出发开始计算从下一站开始剩余的油量
并且把之前欠下的油量也累加起来，看到最后剩余的油量是不是大于欠下的油量。

1. class Solution  

2. {  

3. public:  

4.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost)  

5.     {  

6.         int start = 0;  

7.         int lack = 0;  

8.         int left = 0;  

9.   

10.         for (int i=0; i<gas.size(); i++)  

11.         {  

12.             left += gas[i]-cost[i];  

13.             if (left<0)  

14.             {  

15.                 start = i + 1;  

16.                 lack += left;  

17.                 left = 0;  

18.             }  

19.         }  

20.   

21.         return left + lack >= 0 ? start : -1;  

22.     }  

23. };