CF1978D 题解

KSCD_ · 2024-06-17 11:42:31 · 题解

题意

给出 n 个人的票数 a_i，同时有 c 票暂时没有固定对象。可以让若干人不参加，这些人原有的票数以及 c 票都会投给参加者中编号最小的那个，最终赢家是票数最多的人中编号最小的。对于每个 x\in[1,n]，求出让 i 成为最终赢家最少需要让多少人不参加。

思路

可以把 c 直接加给 a_1，显然跟原题意是等价的。之后求出 a 中最靠前的最大值编号 k，显然 k 的答案为 0。

考虑其他 x 的答案。由于 a_x 本身已经不是最大值，并且即使是去掉目前最大的 a_k，这一部分也会加到编号最小的 a_i 上，最大值一定不降。所以至少要将 x 之前的 x-1 个人全部去掉，才能使 x 为编号最小，a_x 增加以变为最大。

所以维护 a 的前缀和 s，若 s_x\ge a_k，只需要把前面全去掉即可，答案为 x-1。否则需要把前面全去掉，并且把 x 后面的最大值 a_k 也去掉，答案为 x。

代码

#include<iostream>
#define int long long 
using namespace std;
const int N=2e5+10;
int n,c,mx,a[N],s[N];
void sol()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[1]+=c,mx=1;
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+a[i]; 
        if(a[mx]<a[i]) mx=i;
    }
    for(int i=1;i<=n;i++) cout<<(i==mx?0:(s[i]>=a[mx]?i-1:i))<<' ';
    cout<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--) sol();
    return 0;
}