反悔贪心
学习的帖子
反悔贪心 学习笔记 - SyadouHayami - 博客园 (cnblogs.com)
[题解 P3620 【APIO/CTSC 2007]数据备份】 - 野心qwq 的博客 - 洛谷博客 (luogu.com.cn)
写的第一个例题：
[P3620 APIO/CTSC 2007]数据备份 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分析
转换后的题目是：给长度为n-1的序列，不能选择相邻的两个元素，问选择k个元素的最小和。
普通的贪心是，把所有的元素从大到小排列，每次选择最小的元素，并且把它相邻的两个元素打上删除标记表示不能选择。但是显然这样不带反悔的贪心是不行的。
比如对于n=4,k=2的序列2 1 2 9，按照这个贪心来做，会先选到1，并且删除了两个2，之后就只能选择9了，这样显然不是最优解。
”考虑一个反悔的过程，我们需要构造一个方法去消掉之前的贡献转而加为正确的更优的贡献。”
也就是说，我们需要把一个能够消除掉之前选择的影响的点推入这个排序中，和其他普通的贪心选项一起比较，每次选择其中最优的。(由于要动态维护这个顺序，所以用堆/优先队列实现)
在这题里，当选择了位置i的元素$da_i$,则$da_{i-1}$和$da_{i+1}$是不能选择的，但是最优解依旧有可能包含着两个元素，故我们构造一个新的点加入排序，这个点的点权就是：$da_{i-1}+da_{i+1}-da_i$,仔细想想，就是消去了之前选择$da_i$的贡献，并且加上了这个新的选择的贡献。
- 关于为什么是$da_{i-1}$和$da_{i+1}$一起，而不可能是单独选择其中的一个？
因为显然对于这种情况，在优先队列中$da_i$比$da_{i-1}$和$da_{i+1}$更早出现，故$da_{i-1}$和$da_{i+1}$都要比$da_i$小，所以显然着两个要选也是一起选，而不会只选其中一个就把之前的选择$da_i$反悔掉。
在选择了这个代表$da_{i-1}$和$da_{i+1}$的点后，同理也要推入代表$da_{i-1}$和$da_{i+1}$的点。
代码实现
通过双向链表实现了对点的删去，在选择了$da_i$之后，我们把$da_{i-1}+da_{i+1}-da_i$的值存在了原先$da_i$的位置，并且删去了$da_{i-1}$和$da_{i+1}$两个点，并且把反悔新点推入优先队列。
2 1 2 9两个2被删去，并且把反悔点的贡献存在了原先选择的1的位置：
(2) 3 (2) 9这时候$da_i$左右分别和$da_{i-2}$和$da_{i+2}$相连，如果我们之后发现$da_{i-2}$和$da_{i+2}$要比$da_{i-1}$和$da_{i+1}$更优，同样是删去$da_i$左右两侧的两个点，并且把这两个点减去$da_i$的值存入$da_i$，以此类推。
#include<iostream>
#include<queue>
using namespace std;
const int MAXN = 114514;
#define INF 0x3f3f3f3f
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
int da[MAXN],l[MAXN],r[MAXN];//双向连表
bool del[MAXN];
inline void del_lr(int pos){//删除其左右的元素
del[l[pos]] = del[r[pos]] = 1;//打上删除
da[pos] = da[l[pos]]+da[r[pos]]-da[pos];
//双向链表删点
l[pos]=l[l[pos]],r[pos]=r[r[pos]];
l[r[pos]]=pos,r[l[pos]]=pos;//一开始忘了这句即另一边也要接到pos上来
}
//关于为什么是双向链表：
//如果是4 2 1 2 4，选择了1之后,2 2无法选择从链表中删除变成4 3 4,3代表1左右两边的2
//这时候选择3就代表选择了两个2而放弃了1，而选了这两个2就不能选4,3和两个4在链表上也是相邻的
int a[MAXN];
int n,k;
struct Node{
int val,pos;//数值和编号
bool operator < (Node rhs)const{//优先队列要加const
return val>rhs.val;
}
};
priority_queue<Node> q;
void solve(){
cin>>n>>k;
rep(i,1,n) cin>>a[i];
rep(i,1,n-1){
da[i] = a[i+1]-a[i];//相邻做差存入双向链表
l[i] = i-1,r[i] = i+1;
q.push(Node{da[i],i});
}
da[0]=da[n]=INF;//保证了链表两端不会被修改(数值很大一定在堆的尾部)
Node now;
int res = 0;//记录结果
rep(i,1,k){//选择k条线缆
while(del[q.top().pos]) q.pop();//已经被删掉的点还在优先队列里
now = q.top();
q.pop();
res += now.val;//res += da[now.pos]也行
del_lr(now.pos);//删掉左右两边
q.push(Node{da[now.pos],now.pos});//这时候的da[pos]已经是修改过的了
}
cout<<res<<endl;
}
int main(){
//freopen("P3620_2.in","r",stdin);
solve();
}
//反悔贪心例题
//P3620 [APIO/CTSC 2007]数据备份
//https://www.luogu.com.cn/problem/P3620写的第二个例题：
[P4053 JSOI2007]建筑抢修 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题只是蓝题，比第一题要简单点
分析
题目意思是，每个待修理的建筑有两个参数：修理需要的时间和结束时间，必须在结束时间之前修完，问最多有可以修多少个建筑。
先考虑一般的贪心：把建筑根据结束时间进行排序，从小到大考虑若能修$(now+a[i].cost\leq a[i].endt)$就直接修，但是这样显然会有不行的情况，比如
3
100 100
50 200
50 200
//目测最优解为2，但上述贪心为1考虑怎么反悔贪心：
- 可以直接加入的情况$now+a[i].cost\leq a[i].endt$
- 不可以加入，需要考虑反悔的情况$now+a[i].cost>a[i].endt$
考虑每次把点$a[i]$加入修理的集合中时，把$a[i].cost$推入堆中维护最大堆，之后一旦出现不可加入的情况，考虑：
(1)去除堆顶的点后这个点能不能加入,$now-q.top+a[i].cost\leq a[i].endt$
(2)用这个点替换堆顶的点是不是更优(用的时间更少),$a[i].cost<q.top$
代码
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
#define int ll//题目居然不标范围!
typedef pair<int,int> pii;
#define ft first
#define sd second
#define mkp make_pair
const int MAXN = 114514<<1;
int n;
pii a[MAXN];
priority_queue<int> q; //维护当前选择的点中时间最长的
bool cmp(pii a,pii b){
return a.sd<b.sd;
}
void solve(){
cin>>n;
rep(i,1,n) cin>>a[i].ft>>a[i].sd;//按照结束时间排序
//按照时间排序
sort(a+1,a+1+n,cmp);
//rep(i,1,n) cout<<'('<<a[i].ft<<','<<a[i].sd<<')'<<endl;
int nowt = 0;//当前时间
int tmp,cnt;
rep(i,1,n){
if(nowt+a[i].ft>a[i].sd){//时间不够修了
if(!q.empty()){
tmp = q.top();//取需要时间最大的
if(tmp>a[i].ft&&nowt+a[i].ft-tmp<=a[i].sd){//去掉头可以让时间足够
nowt = nowt - tmp + a[i].ft;
q.pop();
q.push(a[i].ft);
}
}
}
else{//时间足够
nowt += a[i].ft;
q.push(a[i].ft);
cnt++;
}
}
cout<<cnt<<endl;
}
signed main(){
solve();
}
// 反悔贪心
// P4053 [JSOI2007]建筑抢修
// https://www.luogu.com.cn/problem/P4053写的第三个例题：
CF436E Cardboard Box - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分析
题意：给n个关卡，要获得w颗星，每个关卡可以支付$a_i$获得1颗星，支付$b_i$获得两颗星，问得到w颗星的最小费用。要求输出选择。
一个假贪心
我先写了一个假的后悔贪心：即选择了$a_i$之后$a_i-b_i$推入堆中，代表反悔第i关选择1个的操作，改成了选2个。
//假的反悔贪心
const int MAXN = 114514<<2;
int n,w;
priority_queue<pii,vector<pii>,greater<pii> > q;
int a[MAXN],b[MAXN],sel[MAXN];
void solve(){
cin>>n>>w;
int cost = 0;
rep(i,1,n){
cin>>a[i]>>b[i];
q.push(mkp(a[i],i));
}
pii tmp;
rep(i,1,w){
tmp = q.top();
q.pop();
if(sel[tmp.sd]==0){
cost += tmp.ft;
q.push(mkp(b[tmp.sd]-tmp.ft,tmp.sd));
sel[tmp.sd] = 1;
}
else{//sel[tmp.sd]==1
cost += tmp.ft;
sel[tmp.sd] = 2;
}
}
cout<<cost<<endl;
rep(i,1,n) cout<<sel[i];
cout<<endl;
}
int main(){
solve();
}这个贪心的问题在于：有些关是一个点非常不划算，两个点非常划算的情况，导致$a_i$根本没机会被选，这样$b_i-a_i$根本没机会加入队列。
正解
首先，根据之前的假算法，我们需要考虑从0星直接变成2星的情况，但是这种情况，选择的星星数量会直接+2，而普通的情况是+1，这样不能进行比较。因此，我们在0星变成2星的时候，同时也要让一个已经做的选择-1，即”i从0星变2星，j从1星反悔成0星“和”i从0星变2星，j从2星反悔成1星“这两种情况。
讨论贪心情况对答案的贡献：
- i从0星变1星：$a_i$
- i从1星变2星：$b_i-a_i$
本来可以只用一条队列维护，但由于后面的反悔选项，因此也需要两条队列，原因一会儿会讲。
讨论两种反悔情况对答案的贡献：
- i从0星变2星，j从1星反悔成0星：$b_j-a_i$
- i从0星变2星，j从2星反悔成1星：$b_j-(b_i-a_i)$
要求得以上两种情况的最优解，需要维护：最小的$b_j$，最大的$a_i$和最大的$b_i-a_i$。需要用到三条队列。
为什么需要五条队列？：
有些关卡星值的修改会牵扯到两个堆，即一个关卡会被推入多个堆中，因此我们在取出了这个关卡的其中一个，并对它进行处理后，另一个堆中的这个关卡的点会变为无效点。我们用sel[i]记录第i关的选项，每次取堆顶之前，先与sel进行比较，把堆顶的无效点都去除（有点像单调队列）。如下：
while(!q1.empty()&&sel[q1.top().sd]!=0) q1.pop();实现细节
- 我们在实现的时候，从5个堆中取出相应的堆顶元素，求出四种方案的解的贡献存进$op1,op2,op3,op4$，再进行比较，选择贡献最小的一个，并把对应的堆顶出栈，再推入更改后的元素。
int minp = 1;
rep(i,2,4)if(op[i]<op[minp])minp=i;//找到4个op中的最优解
res += op[minp];- 更新关卡星数的操作会被重复用，因此可以用函数封装让其更直观，比如，贪心操作1和反悔操作2都会产生新的1星关，故可以用函数add1封装。
inline void add0(int pos){
sel[pos] = 0;
q1.push(mkp(a[pos],pos));//0变1
q3.push(mkp(b[pos],pos));//0变2
}
inline void add1(int pos){
sel[pos] = 1;
q2.push(mkp(b[pos]-a[pos],pos));//1变2
q4.push(mkp(a[pos],pos));//1变0
}
inline void add2(int pos){
sel[pos] = 2;
q5.push(mkp(b[pos]-a[pos],pos));//2变1
}代码
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
typedef pair<int,int> pii;
#define ft first
#define sd second
#define mkp make_pair
#define int long long
#define INF 0x7fffffff
const int MAXN = 114514<<2;
int n,w;
int a[MAXN],b[MAXN],sel[MAXN];
//====贪心操作====
//1.把0星变1星 2.把1星变2星
// ai bi-ai(q2)
//q1维护ai最小值，q2维护bi-ai最小值
//====反悔操作====
//3.把j的0星变2星,再把i的1星变0星 4.把j的0星变2星,再把i的2星变1星
// bj - ai bj - (bi-ai)
//q3维护bj最小值，q4维护ai最大值，q5维护bi-ai最大值
//这样一来便可以处理"1星特别不划算,2星特划算"的情况
priority_queue<pii,vector<pii>,greater<pii> > q1,q2,q3;
priority_queue<pii> q4,q5;
inline void add0(int pos){
sel[pos] = 0;
q1.push(mkp(a[pos],pos));//0变1
q3.push(mkp(b[pos],pos));//0变2
}
inline void add1(int pos){
sel[pos] = 1;
q2.push(mkp(b[pos]-a[pos],pos));//1变2
q4.push(mkp(a[pos],pos));//1变0
}
inline void add2(int pos){
sel[pos] = 2;
q5.push(mkp(b[pos]-a[pos],pos));//2变1
}
inline void solve(){
cin>>n>>w;
int cost = 0;
rep(i,1,n){
cin>>a[i]>>b[i];
q1.push(mkp(a[i],i));
q3.push(mkp(b[i],i));
}
int op[6];
int res=0;
rep(i,1,w){//进行w次选择
op[1]=op[2]=op[3]=op[4]=INF;//四种操作的贡献,找最值
int pos1,pos2,pos3,pos4,pos5;//五个堆的下标暂存
while(!q1.empty()&&sel[q1.top().sd]!=0) q1.pop();
if(!q1.empty()){//0变1
pos1 = q1.top().sd;
op[1] = a[pos1];
}
while(!q2.empty()&&sel[q2.top().sd]!=1) q2.pop();
if(!q2.empty()){//1变2
pos2 = q2.top().sd;
op[2] = b[pos2]-a[pos2];
}
while(!q3.empty()&&sel[q3.top().sd]!=0) q3.pop();
while(!q4.empty()&&sel[q4.top().sd]!=1) q4.pop();
if(!q3.empty()&&!q4.empty()){//0变2,1变0
pos3 = q3.top().sd;pos4 = q4.top().sd;
op[3] = b[pos3]-a[pos4];
}
while(!q5.empty()&&sel[q5.top().sd]!=2) q5.pop();
if(!q3.empty()&&!q5.empty()){//0变2,2变1
pos3 = q3.top().sd;pos5 = q5.top().sd;
op[4] = b[pos3]-(b[pos5]-a[pos5]);
}
int minp = 1;
rep(i,2,4)if(op[i]<op[minp])minp=i;//找到4个op中的最优解
res += op[minp];
if(minp==1){//1.把0星变1星
q1.pop();
add1(pos1);
}
else if(minp==2){//2.把1星变2星
q2.pop();
add2(pos2);
}
else if(minp==3){//3.把j的0星变2星,再把i的1星变0星
q3.pop(),q4.pop();
add2(pos3);
add0(pos4);
}
else if(minp==4){//4.把j的0星变2星,再把i的2星变1星
q3.pop(),q5.pop();
add2(pos3);
add1(pos5);
}
}
cout<<res<<endl;
rep(i,1,n) cout<<sel[i];
cout<<endl;
}
signed main(){
solve();
}
//反悔贪心例题
//CF436E Cardboard Box
//https://www.luogu.com.cn/problem/CF436E
