将每一个点放进一个优先级队列中,每次弹出一个元素后,可以将它两侧的元素加和减去这个元素本身,再将这个元素放进优先级队列中,我们就能实现了对一次选择的反悔,这样贪心的正确性就有了保证
P1792代码
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5; int n,k; int vis[maxn]; struct point { long long l,r,v; }a[maxn]; struct node { int val,id; bool operator <(node other) const { return val<other.val; } }; priority_queue <node> q; long long ans; int main() { // freopen("P1792_1.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d%d",&n,&k); if(n<k*2) { printf("Error!"); return 0; } for(int i=1;i<=n;i++) { scanf("%lld",&a[i].v); a[i].l=i-1; a[i].r=i+1; q.push((node){a[i].v,i}); } a[1].l=n; a[n].r=1; for(int i=1;i<=k;i++) { while(vis[q.top().id]) q.pop(); node tp=q.top(); q.pop(); ans+=tp.val; vis[a[tp.id].l]=vis[a[tp.id].r]=1; a[tp.id].v=a[a[tp.id].l].v+a[a[tp.id].r].v-a[tp.id].v; q.push((node){a[tp.id].v,tp.id}); a[tp.id].l=a[a[tp.id].l].l; a[tp.id].r=a[a[tp.id].r].r; a[a[tp.id].l].r=tp.id; a[a[tp.id].r].l=tp.id; } printf("%lld",ans); return 0; }
P1484代码
#include<bits/stdc++.h> using namespace std; const int maxn=5e5+5; int n,k; int vis[maxn]; struct point { long long l,r,v; }a[maxn]; struct node { int val,id; bool operator <(node other) const { return val<other.val; } }; priority_queue <node> q; long long ans; int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%lld",&a[i].v); a[i].l=i-1; a[i].r=i+1; q.push((node){a[i].v,i}); } for(int i=1;i<=k;i++) { while(vis[q.top().id]) q.pop(); node tp=q.top(); q.pop(); if(tp.val<=0) break; ans+=tp.val; vis[a[tp.id].l]=vis[a[tp.id].r]=1; a[tp.id].v=a[a[tp.id].l].v+a[a[tp.id].r].v-a[tp.id].v; q.push((node){a[tp.id].v,tp.id}); a[tp.id].l=a[a[tp.id].l].l; a[tp.id].r=a[a[tp.id].r].r; a[a[tp.id].l].r=tp.id; a[a[tp.id].r].l=tp.id; } printf("%lld",ans); return 0; }
c/c++开发分享【贪心】P1792 [国家集训队]种树 & P1484 种树地址:https://blog.csdn.net/andyc_03/article/details/107878901
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598185.html