CF847F Solution

题目链接

题解

先处理一定无法入选的情况：将剩下的选票全部给(i)号人仍无法超过排名第(k)的人，或(i)号人无选票且没有剩余选票。然后是一定可以入选的情况：(i)号人有选票，并且使排名前(k+1)中所有选票少于他的人选票超过他所需选票(>m-a)，或者所有人均可入选。其余为有可能入选的情况。

具体实现：统计所有人的选票，设(i)郝人选票为(cnt_i)。将参选人依选票数量降序排序，以求出第(k)个人的选票，(i)号人的排名(rk_i)。(k+1-rk_i)即可求出排名前(k+1)中选票少于(i)号人的数量（(rk_ile k)），超过(i)号人所需选票则为数量( imes cnt_i-)排名([rk_i+1,k+1])区间内选票总和。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
struct node {int id,v,tm;} qwq[N];//排序后的选票,id:参选人原编号,v:选票数,tm:最后一张选票时间
int g[N],cnt[N],rk[N],sum[N];//sum:排序后选票前缀和
bool cmp(node x,node y) {return x.v>y.v || (x.v==y.v && x.tm<y.tm);}
int main()
{
	int n,k,m,a;
	scanf("%d%d%d%d",&n,&k,&m,&a);
	for(int i=1;i<=a;i++) 
	{
		scanf("%d",&g[i]); 
		cnt[g[i]]++; qwq[g[i]].tm=i;
	}
	for(int i=1;i<=n;i++) qwq[i].v=cnt[i],qwq[i].id=i;
	sort(qwq+1,qwq+n+1,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+qwq[i].v,rk[qwq[i].id]=i;
	for(int i=1;i<=n;i++)
	{
		if((rk[i]>k && cnt[i]+m-a<=qwq[k].v) || (!cnt[i] && !(m-a))) printf("3 ");
		else if(cnt[i] && ((rk[i]<=k && (k+1-rk[i])*(cnt[i]+1)-(sum[k+1]-sum[rk[i]])>m-a) || k==n)) printf("1 ");
		else printf("2 ");
	}
	return 0;
}