本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}