题解 P7878 「SWTR-07」My rating is 1064(hard version)

沿用 easy version 的思路:考虑如果到目前已经放了 \(2\) 个集合及以上,那么接下来只要轮换放置就可以避免「用同一个账号连续发出两个帖子」。所以在放了 \(2\) 个集合以后只要找到剩下前 \(k-2\) 大的数放即可。

于是一定是把前 \(x\) 个数放在第一个集合,第 \(x+1\) 放在第二个集合,剩下的选出前 \(k-2\) 大放在剩下集合。

然后直接倒着枚举 \(x\),用堆(priority_queue)维护剩余的前 \(k-2\) 大的数,计算即可。

const int N=500005;
int n,m,T; 
ll a[N];
priority_queue<ll>p;
ll sum,ans;
inline void add(ll x)
{
	sum+=x;
	p.push(-x);
	ll u=-p.top();
	sum-=u;
	p.pop();
}
void work()
{
	n=read(),m=read()-2;
	for (int i=1;i<=n;i++) a[i]=read();
	ll tot=a[1];
	sum=0;
	while (!p.empty()) p.pop();
	for (int i=n-m+1;i<=n;i++) sum+=a[i],p.push(-a[i]);
	for (int i=2;i<=n-m-1;i++) tot-=min(a[i-1],a[i]);
	ans=tot+sum+a[n-m];
	for (int i=n-m-1;i>=2;i--)
	{
		add(a[i+1]);
		tot+=min(a[i],a[i-1]);
		ans=max(ans,tot+sum+a[i]);
	}
	printf("%lld\n",ans);
	return;
}
上一篇:如何在 Angular CLI 创建的项目中自定义 webpack 配置


下一篇:Java pass by reference for Object(LeetCode 39)