【个人学习总结】反悔贪心：反悔堆+反悔自动机

参考：【学习笔记】反悔贪心 - RioTian

---

什么是反悔贪心？

反悔贪心，就是可以回溯的贪心，一般题目我们能使用正常贪心的情况是很少的，因为我们只考虑了局部最优解，我们不能保证局部最优解是最后的最优解，就像买股票，万一后面又涨了呢，那我肯定就要后悔了（

总之，对于此类问题，我们将使用反悔贪心来解决

---

反悔堆

对于某些问题我们将采用最大/小堆来当作中介，以下介绍几种模型

一.“消耗单位时间得非单位价值”求最优解问题

P2949 [USACO09OPEN] Work Scheduling G - 洛谷

思路：

每次我们都可以消耗单位时间来得到 P[i] 的利润，当总消耗时间超过 D[i] 那我们便不能够选取了 P[i]了，对于此题，正常贪心肯定不行，那我们就考虑反悔贪心

首先我们将所有工作按结束时间升序排序，然后我们用一个最小堆优先队列来存储所选的 P[i]，那么对于第 i 个工作我们可以有以下情况

①.如果当前的时间小于等于 work[i] 的截至时间

对于这种情况，我们肯定是直接选比较好（贪心），同时将 P[i] 存储到队列中，以便后续反悔

（此时记得将时间t++，因为我们是真正选了）

②.如果当前的时间大于 work[i] 的截至时间

那我就看堆顶的 P 是否大于 P[i]，如果大于，那我们肯定就要反悔了，毕竟选这个更好，同时再将答案加上二者的差值

（此时时间t就不需要增加了，因为我们是撤销了之前的操作，由于消耗时间都是单位时间，所以相当于没增加也没减少时间）

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlpriority_queue<int,vector<int>,greater<>> pq;struct work
{int time, val;
};void solve()
{int n;cin >> n;vector<work> wk(n);for (int i = 0; i < n; i++){cin >> wk[i].time >> wk[i].val;}sort(wk.begin(), wk.end(), [](work a, work b) {return a.time < b.time; });ll ans = 0;for (int i = 0,t=1; i < n; i++){if (t <= wk[i].time){pq.push(wk[i].val);ans += wk[i].val;t++;}else{int x = pq.top();if (x < wk[i].val){pq.pop();pq.push(wk[i].val);ans += wk[i].val - x;}}}cout << ans;
}
int main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P3093 [USACO13DEC] Milk Scheduling S - 洛谷

思路：

其实和上题一摸一样（不知道为什么难度还不一样）

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlstruct MyStruct
{int g, d;
};void solve()
{int n;cin >> n;vector<MyStruct> cow(n);for (int i = 0; i < n; i++){cin >> cow[i].g >> cow[i].d;}priority_queue<int,vector<int>,greater<>> pq;sort(cow.begin(), cow.end(), [](MyStruct a, MyStruct b) {return a.d < b.d; });ll ans = 0;for (int i = 0, t = 1; i < n; i++){if (t <= cow[i].d){pq.push(cow[i].g);ans += cow[i].g;t++;//真正选了，所以要加时间}else if (!pq.empty()){//反悔操作，相当于撤销原来操作，不增加时间int x = pq.top();if (x < cow[i].g){pq.pop();pq.push(cow[i].g);ans += cow[i].g - x;}}}cout << ans;
}
int main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

---

二.“消耗持续时间得单位价值”求最优解问题

P4053 [JSOI2007] 建筑抢修 - 洛谷

思路：

我们可以像第一类模型一样，我们可以也先按截至时间升序排序，同时我们也用一个优先队列来当中介控制反悔，那么显然，此时我们每个选择都只能得到单位价值，所以我们优先队列就要按照最大堆排序了，且是按每个选择得消耗时间降序排序

为什么？很显然，得X单位价值消耗的时间越少越好，这样才能给后续留有更大的选择空间

所以对于此题，我们可以先升序排序所有任务，然后定义一个所消耗的时间sum，接着枚举所有任务，每次都考虑先选，然后再考虑要不要反悔，那么就有以下情况

①.当前总时间小于等于该任务的截至时间

此时我们肯定要选（贪心）

②.当前总时间大于该任务的截至时间

此时我们就直接将堆顶弹出即可，因为堆顶是耗时最多的元素，同时我们是因为加入新元素才超时的，以此肯定是去除耗时最多的元素最好

而且我们这种先选再考虑的方法也方便了我们反悔，因为可能堆顶最大元素可能就是我们刚刚加入的，所以不需要再比较了

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlstruct MyStruct
{int t1, t2;
};void solve()
{int n;cin >> n;vector<MyStruct> bulid(n);for (int i = 0; i < n; i++){cin >> bulid[i].t1 >> bulid[i].t2;}sort(bulid.begin(), bulid.end(), [](MyStruct a, MyStruct b) {return a.t2 < b.t2; });ll ans = 0, sum = 0;priority_queue<int> pq;for (int i = 0; i < n; i++){sum += bulid[i].t1;pq.push(bulid[i].t1);if (sum <= bulid[i].t2){ans++;}else{sum -= pq.top();pq.pop();}}cout << ans;
}
int main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

---

反悔自动机

相比于反悔堆，反悔自动机更加高级一点，它能够自动的维护我们反悔的操作，通常适用于带限制的决策问题上，不过得想出一种策略以便我们代码执行

CF865D Buy Low Sell High - 洛谷

思路：

对于此题，由于我们只能买一股和卖一股，我们可以考虑以下情况

假如我们每一股都买，那我们考虑如何卖出才最好

显然，如果 x < y 那么此时我们卖出肯定是赚钱的，所以遇到大于自生卖出肯定是赚的

那假如有以下情况呢？

如果 x < y < z，此时如果我们卖出的是 x y这一组合，肯定是不如卖出 x z这一组合的

但是我们之前假设每一股都买了，也就是说我们会这样卖出 y - x + z - y，其实就是z - x

我们注意到y其实是无所谓的，那我们就可以设计一个策略来实现反悔自动机

首先我们先买入股票（这个用作贪心），然后我们判断优先队列中是否有比当前股票大的，

如果有的话，那我们就卖了，同时买入当天的（便于后续反悔）

这样的话每次遇到更好的，我们都能用中间值换取更多的钱

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n;cin >> n;priority_queue<int,vector<int>,greater<>> pq;ll ans = 0;for (int i = 0; i < n; i++){int x;cin >> x;if (!pq.empty()){int t = pq.top();if (x > t){ans += x - t;pq.pop();pq.push(x);}}pq.push(x);}cout << ans;
}
int main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

THE END