题解：P10747 [SEERC 2020] Neo-Robin Hood

这题在 XCPC 模拟赛中出了，然后赛时思路全对，结果代码炸了调不出来，急眼了。

首先看到这是一个需要你制定顺序的题目，考虑微扰贪心，对于只有两个人的情况，我应该偷谁还谁，解除仇恨在本文中称为还钱。

对于两个人，其偷钱和还钱的钱分别为

p_1,m_1,p_2,m_2

，如果我先偷

1

比先偷

2

更优，那么一定要满足

p_1-m_2 \ge p_2-m_1

移项得

p_1+m_1\ge p_2+m_2

，这就是我们的排序方法。

然后考虑如何计算答案，注意到答案显然是有单调性的，所以我们考虑二分答案，我们排完序之后，偷前面的比偷后面的优，所以我们考虑枚举一个断点，使得断点前面的选出

k

个得钱最多的来偷，断点后面的选出

k

个还钱最少的还，这可以使用 priority_queue 来维护，最后判断就做完了。

CPP

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
constexpr int N=1e5+10;
int n,pre[N],suf[N];
struct node{int m,p;}a[N];
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}bool check(int k){
	priority_queue<int> q2;
	priority_queue<int,vector<int>,greater<int> >q1;
	memset(pre,0,sizeof(pre));
	memset(suf,0x3f,sizeof(suf));
	int cnt=0;
	for(int i=1;i<=n;i++){
		q1.push(a[i].m),cnt+=a[i].m;
		if(q1.size()>k) cnt-=q1.top(),q1.pop();
		pre[i]=cnt;
	}cnt=0;for(int i=n;i>=1;i--){
		q2.push(a[i].p),cnt+=a[i].p;
		if(q2.size()>k) cnt-=q2.top(),q2.pop();
		suf[i]=cnt;
	}
//	cout<<"-----------------------\n";
//	cout<<k<<"\n";
//	for(int i=1;i<=n;i++) cout<<pre[i]<<" ";
//	puts("");
//	for(int i=1;i<=n;i++) cout<<suf[i]<<" ";
//	puts("");
	for(int i=k;i+k<=n;i++){
		if(pre[i]>=suf[i+1]) return 1;
	}return 0;
}
signed main(){
	n=reads();
	for(int i=1;i<=n;i++) a[i].m=reads();
	for(int i=1;i<=n;i++) a[i].p=reads();
	sort(a+1,a+n+1,[](node a,node b){return a.m+a.p>b.m+b.p;});
	int L=0,R=n/2,ans=0;
	while(L<=R){
		int mid=(L+R)>>1;
		if(check(mid)) ans=mid,L=mid+1;
		else R=mid-1;
	}printf("%lld\n",ans);
	return 0;
}
/*
5
2 3 4 5 6
1 2 3 4 5
*/

题解：P10747 [SEERC 2020] Neo-Robin Hood

文章操作

相关推荐

评论

题解：P10747 [SEERC 2020] Neo-Robin Hood