codeforces 1904B

2023-12-26 20:35:02

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

题目大意

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

思路

最大的元素一定能消除 n ? 1 n-1 n?1个,因为没有大于最大元素的。
我们不妨求一个 s o r t sort sort之后的前缀和,因为我们最后需要顺序输出,所以先用一个数组 c o p y copy copy一下初始数组
注意,因为前面的元素会对后面的元素造成影响,所以我们从大到小开始处理
因为我们后面要对应输出,所以用个map存答案
从第 n ? 1 n-1 n?1个开始,如果到该元素的前缀和大于等于 a [ n ] a[n] 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;
}

文章来源:https://blog.csdn.net/weixin_70831807/article/details/135228940
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。