分析
- 比 a i a_i ai 小的一定对 a n s i ans_i ansi 有贡献（应该加上）。加上之后 s c o r e score score 变大，在 s c o r e score score 变大的过程中可能会有更多的 a j a_j aj 小于 s c o r e score score 。
- 很容易想到排序，排序之后当前 s c o r e score score 就是 ∑ j = 1 i a j \sum\limits_{j = 1}^ia_j j=1∑iaj ，设 d p i dp_i dpi 表示当前 i i i 往右能覆盖的最多个数。双指针找到最大范围 r r r ，那么 a n s i = r − i + d p i ans_i = r - i + dp_i ansi=r−i+dpi 。
Think Twice, Code Once文章来源地址https://www.toymoban.com/news/detail-808304.html
signed main() {
int T = 1;
T = read();
while (T--) {
int n = read();
vector<pii> a(n + 1);
int sum = 0;
for (int i = 1; i <= n; ++i) {
a[i].first = read(), a[i].second = i;
sum += a[i].first;
}
sort(a.begin() + 1, a.end());
int r = n;
vector<int> dp(n + 1), ans(n + 1);
ans[a[n].second] = n - 1;
for (int i = n - 1; i >= 1; --i) {
sum -= a[i + 1].first;
while (a[r].first > sum) --r;
dp[i] += r - i + dp[r];
ans[a[i].second] = i - 1 + dp[i];
}
for (int i = 1; i <= n; ++i) writesp(ans[i]);
puts("");
}
return 0;
}
文章来源：https://www.toymoban.com/news/detail-808304.html
到了这里，关于codeforces B - Collecting Game的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
