谜一样的牛
题意
有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。
现在这n头奶牛站成一列，已知第i头牛前面有Ai头牛比它低，求每头奶牛的身高。
输入格式
第1行：输入整数n。
第2..n行：每行输入一个整数Ai,第i行表示第i头牛前面有Ai头牛比它低。 （注意：因为第1头牛前面没有牛，所以并没有将它列出）
输出格式
输出包含n行，每行输出一个整数表示牛的身高。
第i行输出第i头牛的身高。
数据范围
1≤n≤1e5
输入样例：
1
2
3
4
5
5
1
2
1
0
输出样例：
1
2
3
4
5
2
4
5
3
1
思路
我们先考虑朴素的算法.我们发现,对于最后一头牛,其身高是一定的,就是a_n + 1,得到了它的身高之后,我们又可以继续推出倒数第二个牛的身高,当然,要考虑最后一头牛的影响.
我们可以维护一个长度为n的布尔类型数组,表示每个身高有没有被认领.然后对于第i头牛,从前往后数身高,当凑够了a_i个比他矮的之后,就将此身高从数组中删除,然后继续看下一头牛.当然,根据上一段的讨论,这里的牛的遍历需要从后往前遍历.
我们从新审视一下先前的思路,我们发现,这本质上是求符合要求的前缀和,如果我们使用树状数组来代替先前的数组,可以在O(logn)的时间内求出截止至某个下标的前缀和,然后我们对整个数组进行二分查找符合要求的前缀和即可.
时间复杂度:对于每个牛都要进行二分查找,每次二分查找都要查询一次前缀和,
所以复杂度是O(nlognlogn)
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
int c[100000+100],a[100000+100],cow[100000+100];
int lowbit(int x){
return x&(-x);
}
int n;
int add(int x,int v){
while(x<=n){
c[x]+=v;
x+=lowbit(x);
}
}
int sum(int x){
int res=0;
while(x>0){
res+=c[x];
x-=lowbit(x);
}
return res;
}
int main(){
cin>>n;
for(int i=0;i<=n;++i){
c[i]=0;
}
for(int i=1;i<=n;++i){
add(i,1);
}
a[1]=0;
for(int i=2;i<=n;++i){
cin>>a[i];
}
for(int i=n;i>0;--i){
int l=1,r=n+1;
while(l<r){
int mid=(l+r)/2;
if(sum(mid)<a[i]+1){
l=mid+1;
}else{
r=mid;
}
}
cow[i]=l;
add(l,-1);
}
for(int i=1;i<=n;++i){
cout<<cow[i]<<endl;
}
return 0;
}
