每次在数组中找大于 \(s\) 的数太麻烦了,将数组排序后,每次能删去的数一定是一个前缀,就只需要对于每个 \(i\),考虑它能删去的数的右端点在哪。设 \(r_i\) 为初始删除 \(i\) 能删到的数的右端点的编号,那么有:
\[r_i=
\begin{cases}
n & \text{ if } i=n \\
i & \text{ if } \sum_{j=1}^{i}a_i<a_{i+1} \\
r_{i+1} & \text{ if } \sum_{j=1}^{i}a_i \geq a_{i+1}
\end{cases}
\]
倒序求 \(r_i\) 即可,每个点的答案就是 \(r_i-1\)。
code:
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+10;
int t,n,r[N],b[N],ans[N];
struct node{int id,x;}a[N];
bool cmp(node x,node y){return x.x<y.x;}
signed main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i].x),a[i].id=i;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)b[i]=b[i-1]+a[i].x;
r[n]=n;
for(int i=n-1;i>=1;i--)r[i]=(b[i]<a[i+1].x?i:r[i+1]);
for(int i=1;i<=n;i++)ans[a[i].id]=r[i]-1;
for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
printf("\n");
}
}