LC871- 最低加油次数

「link」

这题据说是$Google$面试题，百度的笔试题，没有想到贪心+堆确实挺难的。

题目大概的意思是：

从$0$到$target$位置之间有$n$个加油站，每个加油站距离起始点$0$的距离是$x_i$，油量为$y_i$。

问从$0$走到$target$位置最少需要加几次油。

如果从正面考虑到每一个加油站是否加油，都有$2$种选择，那么方案数就有$2^n$种，是不好判断的。

于是我们考虑从后往前看是否能够到达，设在$x_j$位置无法到达，于是就需要在他前面的油站中选择一个加油站$station_i$$(i < j)$。这里比较自然地会想到选油量$y_i$最多的油量。

进而就得到了一个贪心做法，从前往后去遍历，当发现无法走到下一个位置时，就去前面可选择的加油站中选择油量最大的一个加油，如果前面的油站都已经用完但还是无法到达下一个位置，那么就判定不可达，否则记作使用了一次加油次数，直达到达终点。

证明过程如下：

在达到$x_j$位置之前，可以选择的两种方案有：

1. 选择油量最大的加油站；
2. 选择油量不是最大的加油站；

假设最优解是方案2，且最大的加油站没有被用过，那么如果我们将这一次的选择替换成油量最大的加油站，可以发现总的油量只增不减，显然也可以到达下一个油站；

假设是后一次选择了最大油量的油站，那么就需要判断是否可以交换两次顺序：

显然受到影响的只有中间的部分，交换后，对中间部分来说，油量变多，显然可以走到，而对于两侧的而言，总油量不变，也是可以到达。

代码如下：

C++ 复制

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        // 方便起见,可将target位置设成一(target, 0)的加油站
        stations.push_back({target, 0});
        int res = 0;
        priority_queue<int> heap;
        for (auto &station: stations) {
            int x = station[0], y = station[1];
            // 当无法走到下一个位置时,从维护的油站中选择最大的
            while (!heap.empty() && startFuel < x) {
                startFuel += heap.top();
                heap.pop();
                res++;
            }
            // 油站都用完了还是无法到达
            if (startFuel < x) {
                return -1;
            }
            heap.push(y);
        }
        return res;
    }
};