利用网站新媒体宣传法治建设,dw内部网站链接怎么做,网站建设用什么框架好,网站开发业内人士0.写在前面
好久没更了#xff0c;这周是开学第一周 A C M ACM ACM队临时安排讲课任务#xff0c;没人讲#xff0c;我就揽下来这活了。前两天有一道 c f cf cf的 d i v 2 C div2C div2C用到了反悔贪心这个技巧#xff0c;也不需要什么前置算法就可以学#xff0c;所以我…0.写在前面
好久没更了这周是开学第一周 A C M ACM ACM队临时安排讲课任务没人讲我就揽下来这活了。前两天有一道 c f cf cf的 d i v 2 C div2C div2C用到了反悔贪心这个技巧也不需要什么前置算法就可以学所以我第一时间想到的就是讲反悔贪心了顺便更一下好久没更过的博客当备课了。
这个技巧的思维含量不是很高大家可能或多或少在之前无意间用出来过。我第一次了解这个技巧是在去年暑假的时候我的队友跟我说要给我讲一个他新学的小 t r i c k trick trick给我看了一道题洛谷P1484 种树我之前从来没了解过这个小技巧但是做过这个题。
1.随便讲讲
字面意思反悔贪心就是可以反悔的贪心。贪心本身是没有反悔操作的通过对一个问题应用特定的问题选出最优解。然而有时候我们发现贪心只能得到局部最优解这时候可以进行反悔操作。为了实现反悔操作我们要记录下前面操作的最大/最小值等信息因此反悔贪心大多会使用一些数据结构进行实现。
毕竟这只是一个小技巧不是一个算法只靠说大家可能不好理解我们直接进入例题就题分析。
2.例题
CF865D Buy Low Sell High 一个我觉得比较好解释反悔贪心思想的例题 题意对于一支股票你可以知道后面 N N N天这个股票的价格每天可以在两种操作中选一种买入一股该股票、卖出一股之前买入的股票。要求在最后一天手里不能有任何股票。求最后最多能赚多少钱。其中 N ≤ 3 × 1 0 5 N\le 3\times 10^5 N≤3×105。
对于买股票的操作我们观察到题目要求最后一天手里不能有任何股票所以我们只要没有卖出的操作就直接进行买入操作如果最后这支股票卖不出去我们进行反悔这股票我不买了退了就当我那一天没买过。
对于卖股票的操作我们什么时机卖呢肯定是价格高于当前买入但是如果卖亏了怎么办我们选择反悔上次卖的相当于上次不卖了退回来这次再卖。
这就是反悔贪心的思想具体怎么实现呢
我们使用小根堆 q q q来存储买入的价格。
对于第 i i i天价格 a i a_i ai如果该价格不超过当前小根堆堆顶的价格那么我们无法进行卖出操作只能进行买入操作因此将 a i a_i ai入堆即可。此时入堆的 a i a_i ai的意义为记录下当前的买入价格为后续卖出操作准备。
如果该价格超过了当前小根堆堆顶的价格即 a i q . t o p a_iq.top aiq.top意味着我们可以进行卖出操作此时我们就将堆顶元素弹出并将 a i a_i ai入堆该操作堆答案的贡献为 a i − q . t o p a_i-q.top ai−q.top。此时入堆的 a i a_i ai的意义为记录当前卖出的价格为后续反悔操作准备。此时我们会发现如果后续进行了反悔操作那么就相当于这一天没有卖出因此还要将这一天的价格再次入堆此时入堆的 a i a_i ai的意义为填补进行了反悔操作后这一天的空挡。
这样我们就通过用一个小根堆来维护了我们反悔贪心的思想。
代码很短↓
#includebits/stdc.h
using namespace std;
typedef long long ll;
ll ans;
int n;
priority_queueint,vectorint,greaterint q;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;for(int i1,x;in;i){cinx;if(!q.empty()q.top()x)ansx-q.top(),q.pop(),q.push(x);q.push(x);}coutans\n;
}洛谷P1484 种树 一道非常经典的反悔贪心题 题意给定一个长度为 n ( n ≤ 3 × 1 0 5 ) n(n\le3\times 10^5) n(n≤3×105)的序列 a a a第 i i i个数为 a i ( − 1 0 6 ≤ a i ≤ 1 0 6 ) a_i(-10^6\le a_i\le 10^6) ai(−106≤ai≤106)求在该数列中选出不超过 k ( 0 ≤ k ≤ ⌊ n 2 ⌋ ) k(0\le k\le\lfloor\frac{n}{2}\rfloor) k(0≤k≤⌊2n⌋)个数的和最大。限制条件为选了第 i i i个位置的 a i a_i ai就不能选该位置两侧的 a i − 1 a_{i-1} ai−1和 a i 1 a_{i1} ai1。
对问题进行简化取消限制条件即在 n n n个数中选出不超过 k k k个数的和最大。
利用贪心的思想从最大的数开始选直到选满 k k k个数或选到负数为止。
现在回到这个问题如果继续利用之前的贪心的思想很容易举出反例。例如 a [ ] { 2 , 3 , 2 } a[]\{2,3,2\} a[]{2,3,2}从最大的开始选会选到 a 2 3 a_23 a23但是最有策略明显是选择 a 1 a_1 a1和 a 3 a_3 a3贡献为 a 1 a 3 4 3 a 2 a_1a_343a_2 a1a343a2。通过上述例子我们发现选当前位置的两侧和选当前位置 i i i的差值 d a i 1 a i − 1 − a i da_{i1}a_{i-1}-a_i dai1ai−1−ai。如果只考虑这三个位置当 d 0 d0 d0时我们选择两侧的更优当 d 0 d0 d0时我们选择第 i i i个位置更优。
因此考虑反悔贪心我们每次选到 a i a_i ai的时候将 a i a_i ai记录进答案同时将当前位置和两侧的差值 d d d放回 a i a_i ai并将 a i − 1 a_{i-1} ai−1和 a i 1 a_{i1} ai1拿出序列。这样如果我们再次选到了 a i a_i ai这时第 i i i个位置对答案的贡献为第一次的 a i a_i ai和第二次的 d a i 1 a i − 1 − a i da_{i1}a_{i-1}-a_i dai1ai−1−ai总贡献为 a i 1 a i − 1 a_{i1}a{i-1} ai1ai−1其意义是不选择 a i a_i ai选择 a i 1 a_{i1} ai1和 a i − 1 a_{i-1} ai−1。
因此只需要开一个大根堆代表待选的数的集合维护一个 l , r l,r l,r数组代表当前位置的左侧和右侧同时记录已经被选过的位置防止选重即可。时间复杂度为 O ( k log n ) O(k\log n) O(klogn)。
代码↓
#includebits/stdc.h
using namespace std;
const int N 3e5 100;
struct node{int id,w;node(){idw0;}node(int x, int y){idx,wy;}bool operator(const node x) const{return wx.w;}
};
int n,k,a[N],l[N],r[N];
bool vis[N];
priority_queuenode q;
typedef long long ll;
ll ans;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnk;for(int i1;in;i){cina[i];l[i]i-1,r[i]i1;q.push(node(i,a[i]));}for(int i1;ik;i){while(vis[q.top().id])q.pop();node nowq.top();if(now.w0)break;q.pop();ansnow.w;a[now.id]now.wa[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;}coutans\n;}cf1935C Messenger in MAC 最新的用到反悔贪心的cf比赛题 题意有 n ( 1 ≤ n ≤ 2000 ) n(1\le n\le 2000) n(1≤n≤2000)条短信第 i i i条短信包含两个信息 a i a_i ai和 b i ( 1 ≤ a i , b i ≤ 1 0 9 ) b_i(1\le a_i,b_i\le 10^9) bi(1≤ai,bi≤109)读取下标为 p 1 , p 2 , … , p k p_1,p_2,\dots,p_k p1,p2,…,pk的短信所需要的时间为 ∑ i 1 k a p k ∑ i 1 k − 1 ∣ b p k − b p k 1 ∣ \sum_{i1}^{k}a_{p_k}\sum_{i1}^{k-1}\mid b_{p_k}-b_{p_{k1}} \mid ∑i1kapk∑i1k−1∣bpk−bpk1∣。求在给定时间 l ( 1 ≤ l ≤ 1 0 9 ) l(1\le l\le 10^9) l(1≤l≤109)内最多能读取多少条短信。 T ( 1 ≤ T ≤ 5 × 1 0 4 ) T(1\le T\le 5\times10^4) T(1≤T≤5×104)组数据 ∑ n 2 ≤ 4 × 1 0 6 \sum n^2\le 4\times10^6 ∑n2≤4×106。
对问题进行拆分分成两个问题选出第 p 1 , p 2 , … , p k p_1,p_2,\dots,p_k p1,p2,…,pk位置的短信如何安排能使得总时间最短以及如何选出 p 1 , p 2 , … , p k p_1,p_2,\dots,p_k p1,p2,…,pk。
首先第一个问题选出第 p 1 , p 2 , … , p k p_1,p_2,\dots,p_k p1,p2,…,pk位置的短信如何安排顺序能使得总时间最短
观察式子可以发现对于信息 a a a如何安排对时间的贡献是相同的因此只需要考虑信息 b b b不难发现将 b b b按顺序排列是最优的此时所需时间为 ∑ i 1 k a p k b m a x − b m i n \sum_{i1}^k a_{p_k}b_{max}-b_{min} ∑i1kapkbmax−bmin。即对于选出的第 p 1 , p 2 , … , p k p_1,p_2,\dots,p_k p1,p2,…,pk位置的短信我们读取这些短信所需时间为所有短信 a a a的总和加上这些短信的 b b b中最大与最小的差。
对于第二个问题我们考虑到上面化简的式子中如果确定了 b b b的值那么就是选出最小的 a i a_i ai因此我们考虑按 b b b从小到大排序 b b b相同的按 a a a从小到大排序并枚举最小的 b b b。我们的贪心策略是使得 b m a x − b m i n b_{max}-b_{min} bmax−bmin尽可能的小因此先将 b b b相同的选出再去考虑 b b b不同的。对于一个 b b b大于当前 b b b的短信读取它的时间为 a i b − b n o w a_ib-b_{now} aib−bnow。此时在考虑反悔操作如果前面选了 a p a i b − b n o w a_pa_ib-b_{now} apaib−bnow就将 a p a_p ap反悔不进行选择并将当前的 b b b进行更新。通过建一个堆即可维护反悔操作。
赛时代码↓
#includebits/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 s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){s(s3)(s1)(ch15);chgetchar();}xs*w;
}
struct node{int a,b;node(){ab0;}node(int x, int y){ax,by;}
}ms[N];
bool cmp(node x, node y){if(x.b!y.b)return x.by.b;else return x.ay.a;
}
int n,T,nxt[N];
ll l;
void solve(){cinnl;for(int i1;in;i)cinms[i].ams[i].b;sort(ms1,ms1n,cmp);ms[n1]node(0,0);nxt[n]n1;for(int in-1;i;i--){nxt[i]nxt[i1];if(ms[i].b!ms[i1].b)nxt[i]i1;}int ans0;for(int i1;in;i){ll nowms[i].a;int nbms[i].b,cnt1;if(nowl)continue;priority_queueint q;for(int ji1;jnxt[i];j){if(nowms[j].al)nowms[j].a,q.push(ms[j].a),cnt;else break;}ansmax(ans,cnt);for(int jnxt[i];jn;j){if(ms[j].b!nb){nowms[j].b-nb;nbms[j].b;while(nowl!q.empty()){now-q.top();q.pop();cnt--;}if(nowl)break;}if(nowms[j].al)nowms[j].a,q.push(ms[j].a),cnt;else {if(!q.empty()){if(ms[j].aq.top()){nowms[j].a;now-q.top();q.pop();q.push(ms[j].a);}}}ansmax(ans,cnt);}}coutans\n;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinT;while(T--)solve();return 0;
}
