题目链接:https://cn.vjudge.net/problem/POJ-2182
题目大意
n头牛,给出每头牛前面有几个编号比其小的,求出该序列。
分析
倒着看,假设最后一个数前面有i个比它小的,那么它就是第i+1个数,接着将第i+1个数从这n个数中剔除,假设倒数第二个数前面有j个比它小的,那么它就是剩下的数中第j+1个数,以此类推,二分查找树状数组即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 8005;
int n, a[N], ans[N], c[N];
int lowbit(int x)
{
return x & (-x);
}
void updata(int x, int w)
{
while(x < N)
{
c[x] += w;
x += lowbit(x);
}
}
int ask(int x)
{
int sum = 0;
while(x)
{
sum += c[x];
x -= lowbit(x);
}
return sum;
}
int er(int k)
{
int l = 1, r = n;
while(l <= r)
{
int mid = (l + r) >> 1;
if(ask(mid) >= k)
r = mid - 1;
else
l = mid + 1;
}
return l;
}
int main()
{
while(~scanf("%d", &n))
{
memset(c, 0, sizeof c);
a[1] = 0;
updata(1, 1);
for(int i = 2; i <= n; i++)
{
scanf("%d", &a[i]);
updata(i, 1);
}
for(int i = n; i >= 1; i --)
{
int x = er(a[i] + 1);
ans[i] = x;
updata(x, -1);
}
for(int i = 1; i <= n; i++)
printf("%d\n", ans[i]);
}
return 0;
}