Voting Judges(AtCoder agc041

传送门

题意

现在有$N$个题目,每个题目有一个初始票数,$M$个评委,每个评委可以为$V$个不同的题目投票,投票结束之后选择分数前$P$个的题目加入到题目集中,询问某种投票之后使得加入到题目集的题目数最多;

题解

首先将原数组$(a[i])$进行降序排序,那么答案一定是从第$P$个位置开始算起。怎么算呢?记一个前缀数组$b[i]$表示从到达当前位置时,前$i$个位置都投票数变成$a[P]$是花费的总票数。那么从P位置开始枚举,对于每一个票数可以变为$a[P]$的题目进行判断,如果不满足条件就结束。具体判断看代码咯~

AC Code

/******************************* * Coder : He Shuo. * * Type : Original Work * *******************************/ #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 1e5 + 50; ll N,M,V,P; ll a[MAXN],b[MAXN],sum; int main() { scanf("%lld%lld%lld%lld",&N,&M,&V,&P); sum = M * V; for(int i = 1;i <= N;i ++)scanf("%lld",&a[i]); ///降序排序 sort(a + 1,a + 1 + N,greater<ll>()); ll ans = P; ///前P-1道题票数拉满 sum -= (P - 1) * M; ///对于每一个可以票数变为a[P]的题目做前缀和,表示到当前i位置时前面的票数都变成a[P]花费的总票数; for(int i = P;i <= N;i ++) { if(a[i] + M >= a[P])b[i] = b[i - 1] + a[P] - a[i]; else break; } for(ll i = P;i <= N;i ++) { if(a[i] + M >= a[P]) { ll dis = sum - b[i];///剩下多少票没投出去; ll mx = M - (a[P] - a[i]);///到这里还可以共同升多少票; dis -= mx * (i - P + 1);///共同升票剩下的票数; if(dis <= (N - i) * M)ans = i;///若剩下的票数可以尽数投给后面不相干的题目说明可以实现; else break; } } printf("%lld",ans); return 0; }