江门市建设工程安全监督网站,贸易公司如何找客户,新手做电商需要多少钱,网站开发制作合同范本参考#xff1a;【学习笔记】反悔贪心 - RioTian 什么是反悔贪心#xff1f;
反悔贪心#xff0c;就是可以回溯的贪心#xff0c;一般题目我们能使用正常贪心的情况是很少的#xff0c;因为我们只考虑了局部最优解#xff0c;我们不能保证局部最优解是最后的最优解…参考【学习笔记】反悔贪心 - 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
#includecstring
#include iomanip
#includecctype
#includestring
#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_queueint,vectorint,greater pq;struct work
{int time, val;
};void solve()
{int n;cin n;vectorwork 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,t1; 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
#includecstring
#include iomanip
#includecctype
#includestring
#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;vectorMyStruct cow(n);for (int i 0; i n; i){cin cow[i].g cow[i].d;}priority_queueint,vectorint,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
#includecstring
#include iomanip
#includecctype
#includestring
#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;vectorMyStruct 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_queueint 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
#includecstring
#include iomanip
#includecctype
#includestring
#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_queueint,vectorint,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
