1 /************************************************************************* 2 > File Name: GasStation.cpp 3 > Author: zhoukang1991 4 > Mail: zhoukang199191@126.com 5 > Created Time: 2014年08月14日 星期四 02时32分44秒 6 ************************************************************************/ 7 #include <iostream> 8 #include <vector> 9 using namespace std;10 //算法：当出现了sum小于零之后，直接从后面开始判断11 class Solution{12 public:13 int canCompleteCircuit(vector<int> &gas, vector<int> &cost){14 int sum = 0;15 int total = 0;16 int i;17 vector<int> diff;18 for(i = 0 ; i < gas.size() ; ++i){19 diff.push_back(gas[i]-cost[i]);20 }21 int j = -1;22 for(i = 0 ; i < diff.size() ; ++i){23 sum += diff[i];24 total += diff[i];25 if(sum < 0){26 j = i;sum = 0;27 }28 }29 if(total < 0)return -1;30 else return j+1;31 }32 };33 int main(){34 return 0;35 }