(贪心) 反悔贪心之反悔堆

文章目录

⭐例题
- 🚩题意与思路
⭐返回贪心
- 🚩原理（反悔池）
- 🚩落实到题
- 🚩AC code
⭐练习题
⭐END
- 🌟交流方式

⭐例题

经典例题：

871. 最低加油次数

🚩题意与思路

题意：

从 0 开始，给出目的地target和其实油量startFuel。

给出路途中的加油站的坐标和加油量（假设油箱可以无穷大，但每站只能加一次）。

问是否可以到达目的地。

很显然每个加油站都符合“加油”和“不加油”两个属性。很容易想到01背包。

对于本题的数据范围 (5e2) 来说可以使用01背包来处理，但若数据范围增大 (1e4, 1e5)，则会超时。

且本文不是为了讲动规的，因此不多介绍，但还是给出ac的示例代码。

一维 01背包 + 贪心

二维 01背包

⭐返回贪心

🚩原理（反悔池）

准备一个池子，称作反悔池，池中缓存在遍历过程中不断遇到的可选项作为备用资源。

在后续的遍历中，当需要资源的时候，不断的从池中获取，直到满足要求。

基本的原则就如此。

当然这个池子中的值，可以是已经选择了的，也可以是未选择的。都是基于具体题意而言的。

池的数据结构也是基于题目而言比较多样，一般都是堆，栈，队列等可进可出的数据结构。

🚩落实到题

对于本题（871. 最低加油次数），我们用一个堆来进行维护。

使用堆我们可以每次获得池中的最值，也就是我们每次能获得的最大加油量。

到达一个加油站储一次油（加入反悔堆中）。当我们不断要走下一步时，判断是否需要从反悔堆中获得之前没有获取的油。

当堆空了，且未到达目标时就是return -1;。

🚩AC code

当然写法比较多样。

同一种思路或原理，笔者看了下以前的代码发现和现在的实现还是有一定差异的。

下方代码可以AC。

class Solution {
public:int minRefuelStops(int target, int startFuel,vector<vector<int>>& stations) {// 按照距离从小到达排序sort(stations.begin(), stations.end());int sum = startFuel;// 存储可能可以需要的油// 大顶堆，油多的在top// 贪心，每次获取经过地点中最大的priority_queue<int> pool;for (int i = 0; i < stations.size(); i += 1) {const int pos = stations[i][0];const int value = stations[i][1];// 位置＞油箱的历史总量油// 需要从我们的除油池中获取while (sum < pos && !pool.empty()) {sum += pool.top();pool.pop();}if (sum < pos) {return -1;}// 当前这个点可以到，储油pool.push(value);if (sum >= target) {return (i + 1) - pool.size();}}while (sum < target && !pool.empty()) {sum += pool.top();pool.pop();}if (sum < target) {return -1;} else {return stations.size() - pool.size();}}
};