leetcode134 Gas Station

思路：

https://leetcode.com/problems/gas-station/discuss/269604/Java-Greedy-thought-process

关键是要想清楚如果从加油站A出发到不了B，那么从A到B之间的任何一个加油站出发也到不了B。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 class Solution
 4 {
 5 public:
 6     int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
 7     {
 8         int n = gas.size(), sum = 0, start = 0, ans = -1;
 9         for (int i = 0; i < 2 * n; i++)
10         {
11             sum += gas[i % n];
12             sum -= cost[i % n];
13             if (sum < 0) { sum = 0; start = i + 1; }
14             if (i - start == n) { ans = start; break; }
15         }
16         return ans;
17     }
18 };
19 int main()
20 {
21     // int g[] = {1, 2, 3, 4, 5};
22     // int c[] = {3, 4, 5, 1, 2};
23     // int g[] = {2, 3, 4};
24     // int c[] = {3, 4, 3};
25     int g[] = {5, 1, 2, 3, 4};
26     int c[] = {4, 4, 1, 5, 1};
27     vector<int> gas(begin(g), end(g));
28     vector<int> cost(begin(c), end(c));
29     cout << Solution().canCompleteCircuit(gas, cost) << endl;
30     return 0;
31 }