c/c++语言开发共享【贪心】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; }

c/c++开发分享【贪心】P1792 [国家集训队]种树 & P1484 种树地址：https://blog.csdn.net/andyc_03/article/details/107878901