POJ 2182 - Lost Cows

https://asanchina.wordpress.com/2016/01/01/2182-lost-cows/
http://poj.org/problem?id=2182

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 Input

5
1
2
1
0

Sample Output

2
4
5
3
1

我们可以用树状数组代替上面的bool型的array。通过分析上面bool型的array的作用，对于precede[i]，我们想找到这样一个未用的label：比它小的未用的label有precede[i]个。因此我们可以用树状数组和二分查找来做.

可以肯定在树状数组中[read(1), read(2), read(3), read(4), read(5), read(6),…., read(n)]这个数组是一个非递减序列，所以我们二分[1,n]这个范围，取read(mid)，如果read(mid)的值大于precede[i]+1, 那么label一定是在左边范围[1, mid-1]，（当等于的时候也应该是往左边搜索，应为上面的序列是“非递减序列”），otherwise往[mid+1, n]搜索。

int precede[N];
int cow[N];
int tree[N];

void update(int idx, int val)
{
    while(idx <= n) 
    { 
        tree[idx] += val; 
        idx += (idx&-idx); 
    } 
} 

int read(int idx) 
{ 
    int sum = 0; 
    while(idx > 0)
    {
        sum += tree[idx];
        idx -= (idx&-idx);
    }
    return sum;
}
void solve()
{
    memset(tree, 0, sizeof(tree));
    for(int i = 1; i <= n; ++i) 
        update(i, 1); 
    for(int index = n; index >= 1; --index)
    {
        int target = precede[index]+1;
        int low = 1, high = n;
        while(low <= high)
        {
            int mid = (low+high)/2;
            int pre = read(mid);
            if(target == pre)
                high = mid-1;
            else if(target < pre)
                high = mid-1;
            else
                low = mid+1;
        }
        cow[index] = high+1;
        update(high+1, -1);
    }
}

线段树，从后往前扫描，如果当前数字为n，则表示它是剩余的序列中（包括他自己）顺序后的第n+1个数。找到后删除，借助线段树可以达到快速删除的效果

1, 简单的扫描

int n;
int precede[N];
int cow[N];
bool visited[N];

void init()
{
    scanf("%d", &n);
    for(int i = 2; i <= n; ++i) 
        scanf("%d", &precede[i]); 
} 

void solve() 
{ 
    memset(visited, false, sizeof(visited)); 
    for(int index = n; index > 0; --index)
    {
        int pre = 0;
        int i = 1;
        while(pre <= precede[index])
        {
            if(!visited[i])
                ++pre;
            ++i;
        }
        visited[i-1] = true;
        cow[index] = i-1;
    }
    for(int i = 1; i <= n; ++i)
        if(!visited[i])
        {
            cow[1] = i;
            break;
        }
}