加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

这个题上学期的算法课老师出过一个简易版的，只有一个数组既是gas又是cost。而且测试数据很简单所以直接ac了。这个题就直接写不出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int cur_gas = 0;
        int start_index = 0;
        
        while (start_index < n) {
            int j = start_index;
            cur_gas = 0;
            while (j < n + start_index) {
                int station = j % n;
                cur_gas += gas[station] - cost[station];
                if (cur_gas < 0)
                    break;
                j++;
            }
            if (j == n + start_index)
                return start_index;
            start_index = j + 1;
        }
        return -1;
    }
};

这是自己写的，非常臃肿直接TLE。

从gpt学的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();
        int start=0;
        int total=0;
        int current=0;
        cout<<total<<" "<<current;
        for(int i=0;i<n;i++){
            total+=gas[i]-cost[i];
            current+=gas[i]-cost[i];
            if(current<0){
                start=i+1;
                current=0;
            }
        }
        return total>=0?start:-1;
    }
};

代码太简洁了，我什么时候能写出来这样的代码😭

设置当前油量current，总油量total。从0开始遍历，每次total和current都加gas[i]减cost[i]

初始化出发点start=0，如果current<0。说明第i个加油站不能做出发点，start修改为下一个加油站

遍历结束后如果total<0说明一路上的消耗量大于油量，汽车不能往返一周，返回-1

如果total>=0,说明可以往返一周，返回start。

虽然这段路是环形公路，其实和直路没有区别。

如果从i号加油站能到n-1号加油站说明total[i,n-1]>=0.而total[0,i-1]+total[i,n-1] = total >=0可以理解为从[i,n-1]油箱里剩的油>=从[0,i-1]油箱’亏欠‘的油。证明了如果能从i到n-1，则一定能从i出发绕一圈再回到i