codeforces B - Collecting Game

本文主要是介绍codeforces B - Collecting Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分析

• 比 $a_i$ 小的一定对 $an{s}_i$ 有贡献（应该加上）。加上之后 $score$ 变大，在 $score$ 变大的过程中可能会有更多的 $a_j$ 小于 $score$ 。
• 很容易想到排序，排序之后当前 $score$ 就是 $\sum _{j=1}^i{a}_j$ ，设 $d{p}_i$ 表示当前 $i$ 往右能覆盖的最多个数。双指针找到最大范围 $r$ ，那么 $an{s}_i=r-i+d{p}_i$ 。

Think Twice, Code Once

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;
}

这篇关于codeforces B - Collecting Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---