CF1978D Elections

思路

因为有不确定的人，因此对于每个参赛者分两种情况讨论：

• 会获得不确定的票。
• 不会获得不确定的票。

对于第一种，那么当前参赛者 \(i\) 一定是序列中的第一个人，这样才能拿到所有不确定的票，答案先加上 \(i - 1\)。然后 \(a_i\) 就变成了 \(\sum\limits_{j = 1}^{i}a_j + c\)。再去看 \(i + 1 \sim n\) 中 \(> a_i\) 的人（没有就不管），我们只需要删除一个最大的 \(a_j\) 就行了。因为最大的被删了之后会加到 \(a_i\) 上，此时 \(a_i\) 一定 \(\ge\) 序列中所有的数。

对于第二种，因为 \(a_i\) 不能再增大，那么所有 \(>\) 它的数以及在他前面 \(=\) 它的数都要被删掉。但是这些数被删后又会加到下标最小的数上面去，\(a_i\) 就不可能最大了。当然，只有一种数需要判这种情况：序列中第一个最大的数，枚举 \(1 \sim i\) 谁作为第一个数即可。

实现用前缀和，复杂度 \(O(n)\)。

code

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int t;
const int N = 2e5 + 5;
int n;
ll c,a[N];
ll sum[N],k[N];
void solve(){
	cin >> n >> c;
	for(int i = 1;i <= n;++ i) cin >> a[i],sum[i] = sum[i - 1] + a[i];
	ll mx = -1;
	for(int i = n;i >= 1;-- i){
		if(mx <= sum[i] + c) k[i] = 0;
		else k[i] = 1;
		mx = max(mx,a[i]); 	
	}
	bool fl = 0;
	for(int i = 1;i <= n;++ i){
		int ans = 0;
		if(a[i] == mx && !fl){
			fl = 1;
			ans = i - 1;
			for(int j = 1;j <= i;++ j)
				if(sum[j] + c < a[i]){
					ans = j - 1;
					break;
				}
			cout << ans << " ";
			continue;
		}
		ans = i - 1 + k[i];
		cout << ans << " ";
	}
	puts("");
}
int main(){
	cin >> t;
	while(t--) solve();
	return 0;
}