| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 5119 | Accepted: 3210 |
Description
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
* 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
Sample Input
5 1 2 1 0
Sample Output
2 4 5 3 1
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;//树状数组大小
int c[8005];//树状数组
int a[8005];//逆序数
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
{
c[i]+=val;
}
}
int getsum(int x)
{
int cnt=0;
for(int i=x;i>=1;i-=lowbit(i))
{
cnt+=c[i];
}
return cnt;
}
int binary_search(int l,int r,int goal)
{
if(l<r)
{
int mid=(l+r)/2;
int cnt=getsum(mid);
if(cnt==goal) return mid;
else if(cnt>goal) return binary_search(l,mid,goal);
else return binary_search(mid+1,r,goal);
}
else return -1;
}
int main()
{
while(scanf("%d",&n)==1)
{
update(1,1);
a[1]=0;
for(int i=2;i<=n;i++) //这道题是从第2个开始
{
scanf("%d",&a[i]);//输入逆序数
update(i,1);//更新树状数组
}
for(int i=n;i>=1;i--)
{
int j=binary_search(1,n+1,a[i]+1);//二分查找
while(j>=1&&getsum(j)==a[i]+1) j--;j++;
//important 当出现1 2 3 3 3 4这种情况时候 应该找第一个3
a[i]=j;
update(j,-1);//删除节点
}
for(int i=1;i<=n;i++) printf("%d/n",a[i]);
}
return 0;
}