POJ 2182 Lost Cows（算法竞赛进阶指南 ，树状数组，二分查找）

算法竞赛进阶指南，209页， 树状数组，二分查找
题目意思：
n头牛，身高互不相同， 范围是 1 ~ n; n 头牛排成一排，第i头牛，前面有 a[i] 头牛比它矮；
求每头牛的身高；

本题要点：
1、 初始化一个数组b， 每个位置要么是0，要么是1; 用树状数组来维护数组b，
然后从后往前扫描数组a：
1）寻找数组b中第 a[i] + 1 个1的下标， 这个下标就是第i头牛的身高 ans[i]
2）将数组b的第 ans[i] 个1置零。实际就是 树状数组 update(ans[i], -1);
2、 用二分查找来寻找数组b中第 a[i] + 1 个1的下标

#include <cstdio>
#include <cstring>
#include <iostream>
#define lowbit(i) ((i)&(-i))
using namespace std;
const int MaxN = 8010;
int a[MaxN];
int b[MaxN];	//01 序列
int c[MaxN];	//树状数组, 维护数组b的前缀和
int ans[MaxN];
int n;int getSum(int x)
{
    int sum = 0;for(int i = x; i > 0; i -= lowbit(i)){
    sum += c[i];}return sum;
}void update(int x, int v)
{
    for(int i = x; i <= n; i += lowbit(i)){
    c[i] += v;}
}bool judge(int mid, int s)
{
    return getSum(mid) >= s;
}int find_index(int s)
{
    int L = 1, R = n + 1, mid;while(L < R){
    mid = (L + R) / 2;if(judge(mid, s)){
    R = mid;	}else{
    L = mid + 1;}}return L;
}void solve()
{
    memset(c, 0, sizeof c);//初始化树状数组 cfor(int i = 1; i <= n; ++i){
    update(i, 1);}for(int i = n; i >= 1; --i){
    //寻找b数组（01序列）第 a[i] + 1 个 1 的下标ans[i] = find_index(a[i] + 1);	update(ans[i], -1);}for(int i = 1; i <= n; ++i){
    printf("%d\n", ans[i]);}
}int main()
{
    scanf("%d", &n);a[1] = 0;for(int i = 2; i <= n; ++i){
    scanf("%d", &a[i]);}solve();return 0;
}/* 5 1 2 1 0 *//* 2 4 5 3 1 */