本题要进行两个操作:
- 1.从剩余的数中,找出第k个小的数字
- 删除用过的数
发现这个操作符合利用前缀和对数组进行操作的条件,所以使用树状数组进行操作。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,a[N],s[N],ans[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x,int k) //给第x个数加上k
{
for(int i=x;i<=n;i+=lowbit(i)) s[i]+=k;
}
int sum(int x) //计算前k个数的和
{
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=s[i];
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) add(i,1); //每个数都可以使用一次
for(int i=2;i<=n;i++) cin>>a[i];
for(int i=n;i>=1;i--) //从后往前进行遍历
{
int k=a[i]+1; //前面k只牛比本只牛小,说明本只牛的高度是第k+1小
int l=1,r=n;
while(l<r) //利用二分法找到第k小的数
{
int mid=(l+r)>>1;
if(sum(mid)>=k) r=mid;
else l=mid+1;
}
ans[i]=r; //这一只牛的身高为r
add(r,-1); //该数已经使用过,所以删除(-1操作)
}
for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
return 0;
}