题目

Description

有 NN 头奶牛，已知它们的编号为 1∼N1∼N 且各不相同，但不知道每头奶牛的具体编号。

现在这 NN 头奶牛站成一列，已知第 ii 头奶牛前面有 aiai​ 头牛编号小于它，求每头奶牛的编号。

Input

第 11 行，输入一个整数 NN

第 2...N2...N 行，每行输入一个整数 aiai​，表示第 ii 头奶牛前面有 aiai​ 头奶牛的编号小于它（因为第一头奶牛前面没有奶牛，所以 ii 从 22 开始）。

Output

输出包含 NN 行，每行输出一个整数表示奶牛的编号。

第 ii 行输出第 ii 头奶牛的编号。

Sample Input

5
1
2
1
0

Sample Output

2
4
5
3
1

思路

面对从前往后处理无法确定答案；

这道题我们应该想到用倒序处理；

对于样例

$1$   $2$   $1$   $0$；

最后一个数前面比它小的数有$0$个；

所以最后一个数是$1$；

倒数第二个数前面比它小的数有$1$个；

就在剩下未确定的数$2$  $3$  $4$  $5$中寻找第二大的数；

倒数第三个数前面比它小的数有$2$个；

就在$2$  $4$  $5$中寻找第三大的数；

我们假设前面比它小的数个数为$b[i]$，那么这就是剩下未确定的数中的第$b[i]+1$大的数；

剩下的都是如此；

如果数据较大；

处理的方式可以选择线段树；

时间复杂度是$n\log2n$；

方法是把每个节点赋值为$1$；

把每个找到的数删除；

存下被删除的数就好了；

具体看代码~~；

代码

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 const ll _=1e5+1;
 5 ll n,tot;
 6 ll ans[_],b[_];
 7 struct tree
 8 {
 9     ll l,r,v,f;
10 }a[_];
11 void build(ll p,ll l,ll r)//建树
12 {
13     a[p].l=l; a[p].r=r;
14     if(l==r)
15     {
16         a[p].v=1;//赋值为1表示这个数未被确定且这个区间未被确定的数的个数
17         return;
18     }
19     ll mid=(l+r)>>1;
20     ll ls=p*2,rs=p*2+1;
21     build(ls,l,mid);
22     build(rs,mid+1,r);
23     a[p].v=a[ls].v+a[rs].v;
24 }
25 void findout(ll p,ll x)
26 {
27     if(a[p].l==a[p].r)
28     {
29         ans[++tot]=a[p].l;//找到第x大的数并储存
30         a[p].v=0;
31         return;
32     }
33     ll ls=p*2,rs=p*2+1;
34     if(x<=a[ls].v)//如果左子树中未被确定的数大于等于要寻找的第x个数
35         findout(ls,x);//说明要找的数在左子树
36     else
37         findout(rs,x-a[ls].v);//否则在右子树,且x要减去左子树中未被确定的数的个数
38     a[p].v=a[ls].v+a[rs].v;
39 }
40 int main()
41 {
42     scanf("%lld",&n);
43     for(ll i=2;i<=n;i++)//b[1]=0,第一个数前面比它小的数没有
44         scanf("%lld",&b[i]);
45     build(1,1,n);
46     for(ll i=n;i>=1;i--)
47         findout(1,b[i]+1);//前面比它小的数有b[i]个，那么这个数就是剩下未确定的数中的第b[i]+1个数
48     for(ll i=tot;i>=1;i--)
49         printf("%lld\n",ans[i]);
50     return 0;
51 }