学习笔记 反悔贪心

一个我觉得比较好解释反悔贪心思想的例题

题意：对于一支股票，你可以知道后面$N$天这个股票的价格，每天可以在两种操作中选一种：买入一股该股票、卖出一股之前买入的股票。要求在最后一天手里不能有任何股票。求最后最多能赚多少钱。其中$N\le 3\times 10^5$。

对于买股票的操作，我们观察到题目要求最后一天手里不能有任何股票，所以我们只要没有卖出的操作，就直接进行买入操作，如果最后这支股票卖不出去，我们进行反悔，这股票我不买了退了，就当我那一天没买过。

对于卖股票的操作，我们什么时机卖呢，肯定是价格高于当前买入，但是如果卖亏了怎么办，我们选择反悔上次卖的，相当于上次不卖了退回来，这次再卖。

这就是反悔贪心的思想，具体怎么实现呢？

我们使用小根堆$q$来存储买入的价格。

对于第$i$天价格$a_i$，如果该价格不超过当前小根堆堆顶的价格，那么我们无法进行卖出操作，只能进行买入操作，因此将$a_i$入堆即可。此时入堆的$a_i$的意义为：记录下当前的买入价格，为后续卖出操作准备。

如果该价格超过了当前小根堆堆顶的价格，即$a_i>q.top$，意味着我们可以进行卖出操作，此时我们就将堆顶元素弹出，并将$a_i$入堆，该操作堆答案的贡献为$a_i-q.top$。此时入堆的$a_i$的意义为：记录当前卖出的价格，为后续反悔操作准备。此时我们会发现，如果后续进行了反悔操作，那么就相当于这一天没有卖出，因此还要将这一天的价格再次入堆，此时入堆的$a_i$的意义为：填补进行了反悔操作后这一天的空挡。

这样我们就通过用一个小根堆来维护了我们反悔贪心的思想。

代码很短↓

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
int n;
priority_queue<int,vector<int>,greater<int>> q;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=1,x;i<=n;i++){cin>>x;if(!q.empty()&&q.top()<x)ans+=x-q.top(),q.pop(),q.push(x);q.push(x);}cout<<ans<<'\n';
}

一道非常经典的反悔贪心题

题意：给定一个长度为$n(n\le 3\times 10^5)$的序列$a$，第$i$个数为$a_i(-10^6\le a_i\le 10^6)$，求在该数列中选出不超过$k(0\le k\le \lfloor \frac{n}{2}\rfloor )$个数的和最大。限制条件为选了第$i$个位置的$a_i$就不能选该位置两侧的$a_{i-1}$和$a_{i+1}$。

对问题进行简化：取消限制条件，即在$n$个数中选出不超过$k$个数的和最大。

利用贪心的思想，从最大的数开始选，直到选满$k$个数或选到负数为止。

现在回到这个问题，如果继续利用之前的贪心的思想，很容易举出反例。例如 a [ ] = { 2 , 3 , 2 } a[]=\{2,3,2\} a[]={2,3,2}，从最大的开始选会选到$a_2=3$，但是最有策略明显是选择$a_1$和$a_3$，贡献为$a_1+a_3=4>3=a_2$。通过上述例子，我们发现选当前位置的两侧和选当前位置$i$的差值$d=a_{i+1}+a_{i-1}-a_i$。如果只考虑这三个位置，当$d>0$时，我们选择两侧的更优；当$d<0$时，我们选择第$i$个位置更优。

因此考虑反悔贪心，我们每次选到$a_i$的时候，将$a_i$记录进答案，同时将当前位置和两侧的差值$d$放回$a_i$，并将$a_{i-1}$和$a_{i+1}$拿出序列。这样如果我们再次选到了$a_i$，这时第$i$个位置对答案的贡献为第一次的$a_i$和第二次的$d=a_{i+1}+a_{i-1}-a_i$，总贡献为$a_{i+1}+ai-1$，其意义是不选择$a_i$选择$a_{i+1}$和$a_{i-1}$。

因此只需要开一个大根堆，代表待选的数的集合，维护一个$l,r$数组代表当前位置的左侧和右侧，同时记录已经被选过的位置防止选重即可。时间复杂度为$O(k\log n)$。

代码↓

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 100;
struct node{int id,w;node(){id=w=0;}node(int x, int y){id=x,w=y;}bool operator<(const node &x) const{return w<x.w;}
};
int n,k,a[N],l[N],r[N];
bool vis[N];
priority_queue<node> q;
typedef long long ll;
ll ans;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];l[i]=i-1,r[i]=i+1;q.push(node(i,a[i]));}for(int i=1;i<=k;i++){while(vis[q.top().id])q.pop();node now=q.top();if(now.w<0)break;q.pop();ans+=now.w;a[now.id]=now.w=a[l[now.id]]+a[r[now.id]]-a[now.id];q.push(now);vis[l[now.id]]=vis[r[now.id]]=1;l[now.id]=l[l[now.id]],r[now.id]=r[r[now.id]];l[r[now.id]]=r[l[now.id]]=now.id;}cout<<ans<<'\n';}

最新的用到反悔贪心的cf比赛题

题意：有$n(1\le n\le 2000)$条短信，第$i$条短信包含两个信息$a_i$和$b_i(1\le a_i,b_i\le 10^9)$，读取下标为$p_1,p_2,\dots ,p_k$的短信所需要的时间为${\sum }_{i=1}^k{a}_{p_k}+{\sum }_{i=1}^{k-1}\mid b_{p_k}-b_{p_{k+1}}\mid$。求在给定时间$l(1\le l\le 10^9)$内最多能读取多少条短信。$T(1\le T\le 5\times 10^4)$组数据，$\sum n^2\le 4\times 10^6$。

对问题进行拆分，分成两个问题：选出第$p_1,p_2,\dots ,p_k$位置的短信，如何安排能使得总时间最短；以及如何选出$p_1,p_2,\dots ,p_k$。

首先第一个问题：选出第$p_1,p_2,\dots ,p_k$位置的短信，如何安排顺序能使得总时间最短？

观察式子，可以发现对于信息$a$，如何安排对时间的贡献是相同的，因此只需要考虑信息$b$，不难发现将$b$按顺序排列是最优的，此时所需时间为${\sum }_{i=1}^k{a}_{p_k}+b_{max}-b_{min}$。即对于选出的第$p_1,p_2,\dots ,p_k$位置的短信，我们读取这些短信所需时间为所有短信$a$的总和加上这些短信的$b$中最大与最小的差。

对于第二个问题，我们考虑到上面化简的式子中，如果确定了$b$的值，那么就是选出最小的$a_i$，因此我们考虑按$b$从小到大排序，$b$相同的按$a$从小到大排序，并枚举最小的$b$。我们的贪心策略是使得$b_{max}-b_{min}$尽可能的小，因此先将$b$相同的选出，再去考虑$b$不同的。对于一个$b$大于当前$b$的短信，读取它的时间为$a_i+b-b_{now}$。此时在考虑反悔操作，如果前面选了$a_p>a_i+b-b_{now}$，就将$a_p$反悔，不进行选择，并将当前的$b$进行更新。通过建一个堆即可维护反悔操作。

赛时代码↓

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 3e5 + 100;
const int mod = 998244353;
inline void read(int &x){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
struct node{int a,b;node(){a=b=0;}node(int x, int y){a=x,b=y;}
}ms[N];
bool cmp(node x, node y){if(x.b!=y.b)return x.b<y.b;else return x.a<y.a;
}
int n,T,nxt[N];
ll l;
void solve(){cin>>n>>l;for(int i=1;i<=n;i++)cin>>ms[i].a>>ms[i].b;sort(ms+1,ms+1+n,cmp);ms[n+1]=node(0,0);nxt[n]=n+1;for(int i=n-1;i;i--){nxt[i]=nxt[i+1];if(ms[i].b!=ms[i+1].b)nxt[i]=i+1;}int ans=0;for(int i=1;i<=n;i++){ll now=ms[i].a;int nb=ms[i].b,cnt=1;if(now>l)continue;priority_queue<int> q;for(int j=i+1;j<nxt[i];j++){if(now+ms[j].a<=l)now+=ms[j].a,q.push(ms[j].a),cnt++;else break;}ans=max(ans,cnt);for(int j=nxt[i];j<=n;j++){if(ms[j].b!=nb){now+=ms[j].b-nb;nb=ms[j].b;while(now>l&&!q.empty()){now-=q.top();q.pop();cnt--;}if(now>l)break;}if(now+ms[j].a<=l)now+=ms[j].a,q.push(ms[j].a),cnt++;else {if(!q.empty()){if(ms[j].a<q.top()){now+=ms[j].a;now-=q.top();q.pop();q.push(ms[j].a);}}}ans=max(ans,cnt);}}cout<<ans<<'\n';
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--)solve();return 0;
}