[LeetCode問題解]:Gas Station

前言
 
【LeetCode問題解】シリーズ転送ゲート:  http://www.cnblogs.com/double-win/category/573499.html
 
1.タイトルの説明
There are N gas stations along a circular route, where the amount of gas at station i is gas[i] .
You have a car with an unlimited gas tank and it costs cost[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.
2.考え方
問題解:古典的な最大フィールドや問題と同様に、貪欲な戦略を採用しています.
3.解法

 1 class Solution {

 2 public:

 3     int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

 4         int station = gas.size();

 5         int i,sum=0,start=0,total=0;

 6         

 7         for(i=0;i<station;i++)

 8             gas[i]-=cost[i];

 9         

10         for(i=0;i<station;i++) total+=gas[i];

11         if(total<0) return -1;

12      

13        //          ，         

14         for(i=0;i<station;i++)

15         {

16               sum+= gas[i];

17               if(sum<0)

18               {

19                   start=i+1;  //         ，           

20                   sum=0;

21               }

22         }

23         return start;      

24     }

25 };

4.関連テーマ
Maximum Subarray : http://www.cnblogs.com/double-win/p/3746672.html

作者:Double_Win出典:   http://www.cnblogs.com/double-win/p/3746637.html声明:本人のレベルが限られているため、文章の表現とコードの面で不適切な点があれば、批判を歓迎します.