codeforces 1904B
锻炼思维,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;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!