codeforces 1904B

锻炼思维，stl运用等
题目链接

题目大意

给定一个有$n$个元素的数组$a$，存在”初始分数“$x$，当$x>=a[i]$时，分数增加$a[i]$并在数组中删除$a[i]$，分别打印出，当数组$a$中每个元素分别为初始分数时可移除的最大元素数量

思路

最大的元素一定能消除$n?1$个，因为没有大于最大元素的。
我们不妨求一个$sort$之后的前缀和，因为我们最后需要顺序输出，所以先用一个数组$copy$一下初始数组
注意，因为前面的元素会对后面的元素造成影响，所以我们从大到小开始处理
因为我们后面要对应输出，所以用个map存答案
从第$n?1$个开始，如果到该元素的前缀和大于等于$a[n]$那么该元素能消除的数量和下一个元素的数量一样，如果小于，则消除数量为下标数

ACcode

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int M = 2e5 + 9;

void solve() {
    int n;cin >> n;
    vector<ll>a(n + 3), b(n + 3), c(n + 3);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        c[i] = a[i];//记录
    }
    sort(a.begin() + 1, a.begin() + 1 + n);
    for (int i = 1;i <= n;i++)b[i] = b[i - 1] + a[i];
    map<int, int>mp;
    mp[a[n]] = n - 1;
    for (int i = n - 1;i >= 1;i--) {
        if (b[i] >= a[i + 1])mp[a[i]] = mp[a[i + 1]];
        else mp[a[i]] = i - 1;
    }
    for (int i = 1;i <= n;i++)cout << mp[c[i]] << ' ';
    return;
}

int main() {
    int t;cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}