题意：
每头牛有编号，他们乱序排成一排，每头牛只知道前边比自己序号小的有几位。
思路：
递推，最后一只牛的编号是确定的，然后不断进行区间更新，直到找到某个空位前方恰好有n个空位。
这题跟某道排队的题思路是一样的，可以线段树，认为树状数组的解法在时间复杂度上比线段树多了一个logN
因为树状数组只能在logn的复杂度内求解出前n个数字的某些特征，所以需要进行二分不断尝试，直到找到某一个位置前方正好有多少个空位，也就是在二分的过程中使得时间复杂度比线段树要高。线段树直接进行查找就好了，复杂度是logn。
反思：
这道题的WA在二分上，并不是前n个空位中恰好有k个空位就可以安置这头牛，因为有可能这个位置本身就已经有人占据了。所以二分一定要使得两个区间端点会和。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int tree[8005]; int tmp[8005]; int ans[8005]; int n; int lowbit(int a) { return a&(-a); } int solve(int tar) { int sum=0; while(tar>0) { sum+=tree[tar]; tar-=lowbit(tar); } return sum; } int findpos(int tar) { int l=1,r=n; while(l<r) { int mid=(l+r)>>1; if(solve(mid)<tar) { l=mid+1; } else { r=mid; } } return l; } void change(int tar) { while(tar<=n) { tree[tar]--; tar+=lowbit(tar); } } int main() { scanf("%d",&n); tmp[1]=0; for(int i=2;i<=n;i++) { scanf("%d",&tmp[i]); } for(int i=1;i<=n;i++) { tree[i]=lowbit(i); } for(int i=n;i>0;i--) { int tans=findpos(tmp[i]+1); change(tans); ans[i]=tans; } for(int i=1;i<=n;i++) { printf("%d\n",ans[i]); } return 0; }
原文：http://www.cnblogs.com/tun117/p/4963142.html