GDUT-寒假专题训练5--Lost Cows

题目：N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

Input

* Line 1: A single integer, N

* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

Output

* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

Sample

Inputcopy	Outputcopy
51210	24531

题意：知道有n头牛，每头牛知道自己前面有多少头牛比自己矮，求每头牛的高度（第一头牛默认前面没有牛比他高无输入0）

题解：这条题只要从后往前看，只要找出从矮到高的第k+1头牛，并且该牛未被使用过，那么该牛的高度就是我们所求。设定一个数组c初始值为1，表示第i高的牛还剩一头（只有剩一头与剩零头的区别，相当于bool数组），但是这个c用树状数组储存，方便我们查找第k+1头牛。但注意查找的时候要用二分，否则超时。

代码：

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cstdio>

using namespace std;
int c[100001],v,n,mid,k[100001];
inline int lowbit(int a) {return a&-a;}//lowbit求出二进制下该数的最后一个一及其后边的0，返回一个十进制数
inline int sum(int x)//树状数组求和
{
	int ans=0;
	while(x>=1)
	{
		ans=ans+c[x];
		x=x-lowbit(x);
	}
	return ans;
} 

inline void add(int x,int k)//树状数组的加法
{
	while(x<=n){
		c[x]=c[x]+k;
		x=x+lowbit(x);
	}
}

inline int er(int l,int r)
{
	mid=0;
	while(l<r){
		mid=(l+r+1)/2;
		if (sum(mid)>v+1) 
		  r=mid-1;else {if (sum(mid)==v+1&&k[mid]==0) {k[mid]=1;return mid;}
		                if (sum(mid)==v+1&&k[mid]==1) r=mid-1;//保证是恰好等于v+1，否则该牛的高度会偏大
						if (sum(mid)!=v+1) l=mid;}
	}
	k[l]=1;//表示该牛用过
	return l;
}

int main()
{
	mid=0;
	int a[100001]={},b[100001]={},cc[100001]={};
	cin >> n;
	a[1]=0;
	for (int i=2;i<=n;i++) cin >> a[i];
	for (int i=1;i<=n;i++) {add(i,1);cc[i]=i;}//用树状数组储存每一个1
	for (int i=n;i>=1;i--)//后往前
	{
		v=a[i];int vv=er(1,n);//vv是二分查找到的位置
		b[i]=cc[vv];//储存找到的答案，因为是从后往前求，故要倒序输出
		add(b[i],-1);
	}
	for (int i=1;i<=n;i++) cout << b[i] << endl;//记得该牛用完后将其变为0
}