题解：P14374 [JOISC 2018] 糖果 / Candies

此题为 P1792 [国家集训队] 种树的升级版，与原题的区别是此题的序列不是环形的。

考虑使用反悔贪心 + 双向链表。

朴素的贪心是每次选择收益最高的点，并给它左右的节点打上 tag。但有可能出现左右的节点都选的收益比只选这个节点的收益高的情况。

所以我们需要反悔贪心，用大根堆维护当前可进行的操作，选择节点

x

时，删除左右的节点，更新链表，把

x

的权值赋为

v_l + v_r - v_x

，并加入堆。再次选到节点

x

时即为放弃节点

x

，选择

x

节点的左右节点。

对于不是环形这个问题，其实很好解决，只要将

v_0

和

v_{n+1}

赋为

- \infty

就可以避免选到

0

和

n + 1

的情况。

要记得开 long long，否则过不去样例 2。~~别问我是怎么知道的~~

AC CODE

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
ll ans; 
priority_queue<pair<ll,int>>q;
struct node{
	ll val;
	int l,r;
}a[200005];
bool tag[200005];
void del(int x)
{
	a[x].l=a[a[x].l].l;
	a[x].r=a[a[x].r].r;
	a[a[x].l].r=x;
	a[a[x].r].l=x;
}
int main()
{
	cin>>n;
	m=(n+1)/2;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i].val);
		a[i].l=i-1;
		a[i].r=i+1;
		q.push({a[i].val,i});
	}
	a[0].val=a[n+1].val=-1145141919810000;
	for(int i=1;i<=m;i++)
	{
		while(tag[q.top().second])q.pop();
		auto x=q.top();q.pop();
		ans+=x.first;
		tag[a[x.second].l]=tag[a[x.second].r]=1;
		a[x.second].val=a[a[x.second].l].val+a[a[x.second].r].val-a[x.second].val;
		q.push({a[x.second].val,x.second});
		del(x.second);
		printf("%lld\n",ans);
	}
	return 0;
}

题解：P14374 [JOISC 2018] 糖果 / Candies

文章操作

AC CODE

相关推荐

评论

题解：P14374 [JOISC 2018] 糖果 / Candies