原题链接

简单概括

把每个i看成一只怪兽，每只怪兽的初始能量值是\(a[i]\),怪兽可以吃掉其他比自己能量值小的怪兽，并得到进化，能量值增加，增加的大小等于被吃的怪兽的能量值。
问每只怪兽最多能吃几只怪兽？

事实

1.无论如何，一只怪兽一定能吃掉所有初始值比他小的怪兽。
2.在吃完所有初始值比他小的怪兽后，能量值得到增加，有可能吃掉初始值比他还大的怪兽
3.暴力模拟肯定不行，所以我们要考虑优化
4.如果吃掉了初始值比他还大的怪兽\(b\)，相当于能量值变成了“\(b\)吃完所有初始值比\(b\)小的怪兽的能量值”，即若\(i-2\)能吃掉\(i-1\),\(i-1\)能吃掉\(i\),那么\(i-2\)也能吃掉\(i\)

思路

令\(sum[i]\)为基础能量值，\(ans[i]\)为怪兽\(i\)能吃掉的怪兽数量。
\(i=n-1\)开始倒序遍历，如果\(sum[i]>a[i+1]\)，那么\(ans[i]=ans[i+1]\)，并更新\(sum[i]\)
初始值\(ans[n]=n-1\)

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct unit
{
    ll v;
    ll id;
}sc[100005];
bool cmp(unit a,unit b)
{
    return a.v<b.v;
}
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        for(ll i=1;i<=n;i++)
        {
            cin>>sc[i].v;
            sc[i].id=i;
        }
        sort(sc+1,sc+n+1,cmp);
        ll sum[100005]={0};
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+sc[i].v;
        ll ans[100005]={0};
        int cnt=n-1;
        for(int i=n;i>=1;i--)
        {
            if(!(i==n||sum[i]>=sc[i+1].v))cnt=i-1;
            ans[sc[i].id]=cnt;
        }
        for(int i=1;i<=n;i++)printf("%d ",ans[i]);
        puts("");
    }
    return 0;
}