算法
(双指针) $O(n\log n)$
按照 $a$ 从小到大的顺序用双指针模拟一下即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<int> ai(n);
rep(i, n) ai[i] = i;
sort(ai.begin(), ai.end(), [&](int i, int j) { return a[i] < a[j]; });
vector<int> ans(n);
ll now = 0;
for (int i = 0; i < n;) {
now += a[ai[i]];
int j = i+1;
while (j < n and now >= a[ai[j]]) {
now += a[ai[j]];
++j;
}
for (int k = i; k < j; ++k) ans[ai[k]] = j-1;
i = j;
}
rep(i, n) cout << ans[i] << " \n"[i == n-1];
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}