题目描述

有注释。

C++ 代码

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

const int N=1e5+10;

/*
    暴力枚举是O(n^2)，必过不去；
    可以想到利用树状数组优化到O(nlogn)左右；

    如果建立树状数组，且b[i]=1; 查询成功则置为0；

    这样，对于 第 i 个牛， 它的排序就是 把 i 之后 所有牛的位置置 0 之后，前缀和刚好等于 h[i]+1 的位置。

    则可以用前缀和表示在未选的牛中，身高的位次（动态）；
    这时由前缀和的单调性，必有二分性，二分的去查找k的位置;
    综上，时间复杂度为O(nlognlogn);也是可以过掉的。
*/

int n;
int h[N];
int ans[N];
int tr[N];

int lowbit(int x)
{
    return x& -x;
}

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int main()
{ 
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d",&h[i]);

    for(int i=1;i<=n;i++)  tr[i]=lowbit(i);  //初始化；add(i,1)也可以；

    for(int i=n;i;i--)      //逆序二分
    {
        int k=h[i]+1;   // k 代表当前 牛 的序号
        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(sum(mid)>=k) r=mid;  //找最小的符合条件的数，左二分。
            else l=mid+1;
        }
        ans[i]=r;   
        add(r,-1);  //置零
    }

    for(int i=1;i<=n;i++)
    {
        printf("%d\n",ans[i]);
    }

    return 0;
}