概述
1、什么是反悔贪心？
贪心本身是没有反悔操作的，贪心求的就是当前的最优解。但当前的最优解有可能是局部最优解，而不是全局最优解，这时候就要进行反悔操作。
另外的来自蒟蒻dalao的解释：
众所周知，正常的贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。也就是说我们的每一步都是站在当前产生的局面上所作出的最好的选择，是没有反悔操作的。
不加反悔的一直朝着当前局面的最优解走很可能导致我们被困在局部的最优解而无法到达全局的最优解，就好像我们爬山就只爬到了一座山的山顶却没有到整片山的最高处：
但是反悔贪心允许我们在发现现在不是全局最优解的情况下回退一步或若干步采取另外的策略去取得全局最优解。就好像我们站在的一座山的山峰上，看到了还有比我们现在所在位置还高的山峰，那我们现在就肯定不是在最高的地方了，这时我们就反悔——也就是下山再爬上那座更高的山：
这就是反悔贪心的大致思路。根据反悔记录操作的不同，反悔贪心又分为反悔堆和反悔自动机。
总的来说：反悔操作指的是这一步的贪心不是全局最优解，我们就退回去一步（人工或自动判断），换一种贪心策略。按照判断方式的不同可以分为反悔自动机和反悔堆两种方法。
-
反悔自动机：
即设计一种反悔策略，使得随便一种贪心策略都可以得到正解。
基本的设计思路是：每次选择直观上最接近全局最优解的贪心策略，若发现最优解不对，就想办法自动支持反悔策略。（这就是自动机的意思）
具体题目具体分析。一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的。
-
反悔堆：
即通过堆（大根堆、小根堆）来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。
由于堆的性质，使得堆的首数据一定是最优的，这就可以实现快速更新最优解。
2、例题以及代码
反悔堆
用时一定模型
USACO09OPEN 工作调度Work Scheduling
Description:
有 nn 项工作，每 ii 项工作有一个截止时间 DiDi ，完成每项工作可以得到利润 PiPi ，求最大可以得到多少利润。
Method:
尽管这道题直接理解会感觉简单，实则不然。
对于简单贪心：
第一种贪心是开一个桶，对于每一个截止日期我们都只保留能产生价值最大的任务去做，其余的不去做。这种方法很明显是错误的，我们可以举出一个例子来否定这个策略。比如我们只有两个任务A和B，A任务的截止日期是3，价值是3；B的截止日期是3，价值是1。按照我们的贪心策略，我们就舍弃B选择A，但是实际上，我们可以在时间2去做B，时间3去做A这样就可以全都要，明显比只做A会好得多，所以这种贪心策略是不可取的。
第二种贪心就更加明智一点，我们都有一种直觉那就是先完成比较紧急的任务亦或者说先完成截止日期靠前的任务会更加优。所以我们就按照截止日期(从小到大)为第一关键字，价值(从大到小)为第二关键字进行排序，然后顺序遍历每个任务，能做就做，不能做(当前已安排任务数=当前任务的截止日期)就直接抛弃。这样做看起来很有道理，但实际上有有可能到后期都是高报酬的工作（但由于前期做了太多价值很低的任务导致都超时做不了了）就会让答案不是很优秀。比如我们举个例子。加入我们有四个任务A、B、C、D.其中A任务的截止日期为1，价值为2；B的截止日期为1，价值为1；C的截止日期为2，价值为5；D的截止日期为2，价值为6。按照我们现在的贪心策略，我们会排序后按照ABDC的顺序进行考虑，然后选择AD这两个任务去完成最后结果是8。但实际上，如果我们不去做A，而是把做A的时间拿去做C，这样我们最后的结果就是11是优于我们的贪心答案的。
为什么会出现这样的问题呢？是因为到了后期，我们见到了很多高回报的工作但是能做的却很有限了，这又是因为前期做了很多价值很低的任务，换句话说我们可能会后悔前期做了些低报酬的工作。那我们能不能反悔，也就是退掉之前低报酬的工作用那个时间去完成高报酬的工作呢？这就要用到我们的反悔堆。
当然我们还有第三种贪心，以价值为关键字从大到小排序，假如我们考虑第i个任务做不做，如果从1∼t[i]（第i个任务的截止时间） 没有塞满，那就尽量咕到最后一个空位做，正确也是显然的，但是直接暴力是 O(n2)O(n2) 的。然后我们发现找空位的过程可以优化，加入树状数组，二分位置判断即可，时间复杂度 O(nlog2n)O(nlog2n) 即可以通过。
反悔贪心：
假如满足题设条件（即没有超出截止时间）就分成两种情况：若当前的最优解比原来的最优解（堆顶）更优秀，我们就更新全局最优解，把原来的最优解丢出去，再把当前的最优解放进去（即反悔策略）；反之，就不管了。假如不满足特设条件，就把当前的最优解丢进堆里，更新全局最优解即可。
// RioTian 21/03/10 学习自 蒟蒻dalao
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
int deadline, value;
//重载<号的定义，规定堆为关于价值的小根堆
bool operator<(const node &v) const {
if (value > v.value) return true;
return false;
}
} a[110000];
// 使用优先队列代替手写堆(节省Coding时间)
priority_queue<node> q;
int n;
ll ans = 0;
//自定义排序函数，将任务按截止时间从小到大排序
bool cmp(node x, node y) {
if (x.deadline < y.deadline) return true;
return false;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].deadline >> a[i].value;
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; ++i) {
//如果当前决定做的任务数小于截止日期也就是还有时间做当前任务
if (a[i].deadline > q.size()) {
ans += a[i].value;
q.push(a[i]);
} else {
if (a[i].value > q.top().value) {
ans -= q.top().value;
q.pop();
q.push(a[i]), ans += a[i].value;
}//反悔操作
}//考虑是否反悔，不做之前做的任务
}
cout << ans << "n";
return 0;
}
价值一定模型
模型总结来自蒟蒻dalao，万分感谢！
Description:
我们再来考虑这样一个问题，我们有 nn 个任务( n≤1e5n≤1e5 )，并且每个任务都有两个属性——截止日期和完成耗时。在截止日期前完成任务就可以得到这个任务产生的价值。在同一时间我们只能去做一个任务。所有任务的价值都是一样的，问我们最后最多能完成多少个任务。
算法讲解
有了刚刚那题的基础，我们也很容易可以考虑到反悔贪心的反悔堆模型上。由于我们需要反悔操作，而反悔操作是建立我们能够反悔——不做之前决定做的任务而去做当今决定做的任务，所以首先我们肯定还是要按照截止日期从小到大进行排序。
在我们上面讲到的用时一定的模型中，我们用堆维护“性价比”最低的任务也就是我们价值最低的任务用于反悔操作。在这个问题中，我们同样用堆去维护“性价比”最低的任务。由于每个任务的价值是一定的，所以我们性价比最低的任务就是耗时最长的任务，如果我们不做耗时比较长的任务去做耗时比较短的任务，我们就能留下更多的时间给后面的任务，又由于每个任务的价值是一样的，所以这样做的正确性也是显然的。
所以具体来说我们就开一个大根堆维护已选任务的时间，堆顶就是耗时最长的任务。我们顺次考虑排序后的每个任务，当前决定要做的任务的总耗时加上现在这个任务的耗时小于等于现在这个任务的截止时间，那我们就直接做，把现在这个任务丢进堆里，总耗时加上现在这个任务的耗时就可以了。但如果当前决定要做的任务的总耗时加上现在这个任务的耗时大于现在这个任务的截止时间呢，我们就考虑是否进行反悔操作替换决定做的任务。我们看一看堆顶任务的耗时和现在这个任务的耗时，如果堆顶任务的小那就不替换；如果当前任务的耗时小，我们就用当前任务替换掉堆顶任务就好啦。
模板代码
这道题也是有模板题的，题目是[JSOI2007]建筑抢修，下面附上模板代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
int deadline, time;
//重载<号的定义，规定堆为关于耗时的大根堆
bool operator<(const node &v) const {
if (time < v.time) return true;
return false;
}
} a[160000];
// 使用优先队列代替手写堆(节省Coding时间)
priority_queue<node> q;
int n;
ll last = 0;
//自定义排序函数，将任务按截止时间从小到大排序
bool cmp(node x, node y) {
if (x.deadline < y.deadline) return true;
return false;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].time >> a[i].deadline;
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; ++i) {
//如果决定做的任务耗总时加上当前任务耗时小于等于当前任务截止时间
if (a[i].deadline >= last + a[i].time) {
last += a[i].time;
q.push(a[i]);
} else {
//如果堆顶耗时大于当前考虑任务的耗时
if (a[i].time < q.top().time) {
last -= q.top().time;
q.pop();
q.push(a[i]), last += a[i].time;
} //反悔操作
} //考虑是否反悔，不做之前做的任务
}
cout << q.size() << "n";
return 0;
}
反悔自动机
相比于反悔堆，反悔自动机更加高级一点，它能够自动的维护我们反悔的操作，通常适用于带限制的决策问题上。
举例：假如我们有四个数ABCD，AB当中只能选一个，CD当中只能选一个，问我们最后能收获的最大价值是多少。
假如刚开始我们选的是AC，那我们就可以把AC先删掉，把的值B变成B-A，D的值变成D-C，接下来的选择不考虑任何束缚。这样如果我们接下来再去选B，那这时我们选的值其实是B-A，加上之前选的A，相当于我们选了B没有选A，这就完成了返回操作——通过修改关联点的值让我们做到不选之前决定选的点而去选现在这个点。
这就是反悔自动机的大致思路。具体的反悔自动机又分为堆反悔自动机和双向链表反悔自动机两种，这样讲可能有点抽象，我们下面通过几个例题来看看反悔自动机的具体运用。
堆反悔自动机
CF865D Buy Low Sell High（堆反悔自动机）
Description:
已知接下来 nn 天的股票价格，每天可以买入当天的股票，卖出已有的股票，或者什么都不做，求 nn 天之后最大的利润。
Method：
我们先从简单的贪心开始考虑。首先我们可以贪心地对于每一天 i，如果我们可以卖出，那么贪心的选择之前的价格最小的一天 j，然后若 Pj<PiPj<Pi 就可以在 j 天买入一股，然后在第 i 天卖出，这时候就仅需要一个 priority_queue 就可以了。
但是还有一个问题，如何考虑下面这组数据呢？
1 2 5
可以发现，若贪心处理，则仅会在第 1 天买入一股，并在第 2 天卖出，赚到了 1 元。但是若将第 1 天的股票在第 3 天卖出，则可以获得高达 4 元的利润，比原答案不知道高到哪里去了。
所以我们尝试去考虑设计一种反悔策略，使所有的贪心情况都可以得到全局最优解。（即设计反悔自动机的反悔策略）
定义 CbuyCbuy 为全局最优解中买入当天的价格，CsellCsell 为全局最优解中卖出当天的价格，则：
Csell−Cbuy=(Csell−Ci)+(Ci−Cbuy)Csell−Cbuy=(Csell−Ci)+(Ci−Cbuy)
CiCi 为任意一天的股票价格
即我们买价格最小的股票去卖价格最大的股票，以期得到最大的利润。我们先把当前的价格放入小根堆一次（这次是以上文的贪心策略贪心），判断当前的价格是否比堆顶大，若是比其大，我们就将差值计入全局最优解，再将当前的价格放入小根堆（这次是反悔操作）。相当于我们把当前的股票价格若不是最优解，就没有用，最后可以得到全局最优解。
上面的等式即被称为反悔自动机的反悔策略，因为我们并没有反复更新全局最优解，而是通过差值消去中间项的方法快速得到的全局最优解。
Code:
struct node {
int value;
// 重载<号的定义，规定堆为关于价值的小根堆
bool operator<(const node &b) const {
if (value > b.value) return true;
return false;
}
} a[330000];
priority_queue<node> q;
int n;
ll cnt = 0;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].value;
for (int i = 1; i <= n; ++i) {
q.push(a[i]); //用于贪心买价格最小的股票去买价格最大的股票
//假如当前的股票价格不是最优解
if (q.size() && q.top().value < a[i].value) {
cnt += a[i].value - q.top().value; //将差值计入全局最优解
// 将已经统计的最小的股票价格丢出去，并执行反悔策略：将当前的股票价格再放入堆中，即记录中间变量（等式中间的Vi)
q.pop(), q.push(a[i]);
}
}
cout << cnt << "n";
return 0;
}
双向链表反悔自动机
BZOJ2151 种树（双向链表反悔自动机）
Description:
有 nn 个位置，每个位置有一个价值。有 mm 个树苗，将这些树苗种在这些位置上，相邻位置不能都种。求可以得到的最大值或无解信息。
Method：
先判断无解的情况，我们显然可以发现，若 m>n2m>n2 ，则是不能在合法的条件下种上 m 棵树的，故按题意输出Error!即可。
假如有解的话，我们可以很轻松的推出贪心策略：在合法的情况下选择最大的价值。
显然上面的策略是错误的，我们选择了最大价值的点，相邻的两个点就不能选，而选择相邻两个点得到的价值可能更大。
考虑如何设计反悔策略。
我们同样用差值来达到反悔的目的。假设有 A，B，C，DA，B，C，D 四个相邻的点（如图）。
AA 点的价值为 aa ，其他点同理。若
a+c>b+da+c>b+d
则：
a+c−b>da+c−b>d
假如我们先选了 BB 点，我们就不能选 AA 和 CC 两点，这显然是不对的，但我们可以新建一个节点 P,PP,P 点的价值为 a+c−ba+c−b，再删去 BB 点。（如图，红色的是删去的点，橙色的新建的点)
下一次选择的点是 P 的话，说明我们反悔了（即相当于 B 点没有选），可以保证最后的贪心最优解是全局最优解。
如何快速插入 P 点和找出是否选择 P 点呢？我们可以使用双向链表和小根堆，使得最终在 O(nlogn)O(nlogn) 的时间复杂度下快速求出全局最优解.
注意点：
- 一定要记录这个点选没有选过，假如已经选过了，就从堆中丢出去；
- 1 与 n 是相邻的，一定要特判一下；
- 双向链表一定不要写挂了；
- 一定要先将新建的点的价值存入一开始的价值数组，再丢进堆里；（不然会卡数据）
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e6 + 10;
struct node {
int val, id;
bool operator<(const node& x) const { return val < x.val; }
} now, x;
ll val[N]; // 价值
ll vis[N], l[N], r[N]; // vis记录是否删除,l、r为双向链表的左右点
int t, n, m;
ll ans = 0;
priority_queue<node> q;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> val[i];
while (q.size()) q.pop();
// 初始化堆
for (ll i = 1; i <= n; ++i) {
now.id = i, now.val = val[i];
vis[i] = 0;
q.push(now);
}
// 处理双向链表
for (int i = 2; i <= n; ++i) l[i] = i - 1;
for (int i = 1; i <= n; ++i) r[i] = i + 1;
l[1] = r[n] = 0;
for (int i = 1; i <= m; ++i) {
x = q.top(), q.pop();
while (vis[x.id] == 1) { //找到一个没有被删除的值最大的点
x = q.top(), q.pop();
}
if (x.val < 0) break;
ans += x.val;
if (l[x.id] != 0) vis[l[x.id]] = 1; //删除左边的点
if (r[x.id] != 0) vis[r[x.id]] = 1; //删除右边的点
if (l[x.id] != 0 && r[x.id] != 0) {
now.id = x.id;
now.val = val[x.id] = val[l[x.id]] + val[r[x.id]] - val[x.id];
r[l[l[x.id]]] = x.id;
l[x.id] = l[l[x.id]];
l[r[r[x.id]]] = x.id;
r[x.id] = r[r[x.id]];
q.push(now);
} else if (l[x.id])
r[l[l[x.id]]] = 0;
else
l[r[r[x.id]]] = 0;
}
cout << ans << "n";
return 0;
}
转载大佬代码，
反悔贪心太强了
链接：
https://www.cnblogs.com/RioTian/p/14513549.html
最后
以上就是细心鸡为你收集整理的反悔贪心的全部内容，希望文章能够帮你解决反悔贪心所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复