简单概括
把每个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;
}