[ABC373E] How to Win the Election

WuMin4 / 2024-10-23 / 原文

[ABC373E] How to Win the Election

思路

比较难调的二分。

将 $A$ 数组排序，很容易想到对于每个 $i$ 二分 $X$。检查 $X$ 是否成立可以贪心。一开始 $A_j>A_i+X$ 的人要先算进满足人数，剩下的人可以二分，对于第 $x\sim y$ 人要满足 $A_x,A_{x+1}\cdots A_y>A_i+X$ 所需的最小票数即为 $(y-x+1)\times(A_i+X+1)-\sum_{z=x}^y A_z$，可以前缀和优化，最后判断满足人数是否 $\le M$ 即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,c[200005],ans[200005],b[200005];
struct node{
	int x,id;
}a[200005];
bool cmp(node x,node y){
	return x.x<y.x;
}
bool check(int x,int md){
	int ls=lower_bound(b+1,b+1+n,a[x].x+md+1)-b;
	int sy=m-(n-ls+1),syp=k-md;//sy为剩下的人，syp为剩下的票
	//减去本身大于x获得的票数的人
	if(sy<=0) return 0;
	int l=x+1,r=ls,ANS=0,mid;
	while(l<=r){
		mid=(l+r)/2;
		if((ls-mid)*(a[x].x+md+1)-(c[ls-1]-c[mid-1])<=syp)
			r=mid-1,ANS=mid;
		else
			l=mid+1;
	}
	if(ANS!=0)
		sy-=(ls-ANS),syp-=(ls-ANS)*(a[x].x+md+1)-(c[ls-1]-c[ANS-1]);
	else
		return 1;
	if(sy<=0) return 0;
	l=1,r=x-1,mid,ANS=x;
	while(l<=r){
		mid=(l+r)/2;
		if((x-mid)*(a[x].x+md+1)-(c[x-1]-c[mid-1])<=syp)
			r=mid-1,ANS=mid;
		else
			l=mid+1;
	}
	sy-=(x-ANS);
	if(sy<=0) return 0;
	//以i为分界线分两段二分
	return 1;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i].x,k-=a[i].x,a[i].id=i;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
		c[i]+=a[i].x,b[i]=a[i].x;
	for(int i=1;i<=n;i++)
		c[i]+=c[i-1];//处理前缀和
	for(int i=n;i>=1;i--){
		int l=0,r=k,mid,ANS=-1;
		while(l<=r){//二分额外获得的票
			mid=(l+r)/2;
			if(check(i,mid))
				r=mid-1,ANS=mid;
			else
				l=mid+1;
		}
		ans[a[i].id]=ANS;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	return 0;
}