LC871- 最低加油次数

「link」

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

题目大概的意思是：

image-20220702083343295

从\(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，且最大的加油站没有被用过，那么如果我们将这一次的选择替换成油量最大的加油站，可以发现总的油量只增不减，显然也可以到达下一个油站；

image-20220702085312148

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

image-20220702085727127

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

代码如下：

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;
    }
};