【贪心】P1792 [国家集训队]种树 & P1484 种树

将每一个点放进一个优先级队列中，每次弹出一个元素后，可以将它两侧的元素加和减去这个元素本身，再将这个元素放进优先级队列中，我们就能实现了对一次选择的反悔，这样贪心的正确性就有了保证

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;
}