POJ2182 Lost Cows 题解

题目

有(N)((2 <= N <= 8,000))头母牛,每头母牛有自己的独一无二编号((1..N)).

现在(N)头母牛站成一列,已知每头母牛前面编号比它小的母牛数量,求每头母牛的编号.

输入格式

第1行 : 一个整数 (N)

第2..N行 : 从第2头母牛到第N头母牛的前面编号比它小的母牛数量

输入样例

输出样例

题解

先手造一组数据

2 1 5 4 3  // 编号序列

设比第(i)头牛前面比它编号小的牛的数量为(A_i),编号为(B_i)

可以发现,最后一头牛编号为3,前面有2头编号比它小的牛.因为所有编号比它小的点都在前面,所以,(B_N=A_N+1)

同理,对于倒数第二头牛

若(A_{N-1}<A_N),则(B_{N-1}=A_{N-1}+1),唯一在它后面的第(N)头牛编号比它大,所以所有编号比它小的点都在前面,例如 :

3 4 2 1 5 // 编号序列

因为(0=A_4<A_5=4),则(B_4=A_4+1=0+1=1)

若(A_{N-1}>A_N),则(B_{N-1}=A_{N-1}+2),相比第一条,最后一头牛编号也比它小,额外加上1,例如 :

3 4 2 5 1  // 编号序列

因为(3=A_4>A_5=0),则(B_4=A_4+2=3+2=5)

因为第i头牛前面有(A_i)头牛编号比它小,所以(B_i)至少是(A_i+1)(也就是从第(1)到第(i-1)头牛都在这头牛的前面的情况),如果后面的牛还有比它小的,那么这头牛的编号又要增加,所以(B_i)为(1..N)中去掉(B_{i+1})..(B_N)中的数后从前往后的第(A_i+1)个数

建立一个长度为(N)的数组c,初始化为(1)

因为要去掉后面的数,所以从后往前扫描(A_i),对于每个(A_i),查询该数组中第(A_i+1)个"1"的位置,此位置的下标就是(B_i),然后(c[B_i]=0),这是在去掉(B_{i+1})..(B_N)中的数

使用样例数据模拟一遍

 0 1 2 1 0  // A序列(省略A[0])

开始扫描

 1 1 1 1 1  // c数组(省略c[0])

第一次 : (A_5=0),第(0+1)个"1"的下标为(1),则(B_5=1)

[0]1 1 1 1  // c数组(省略c[0])

第二次 : (A_4=1),第(1+1)个"1"的下标为(3),则(B_4=3)

 0 1[0]1 1  // c数组(省略c[0])

第三次 : (A_3=2),第(2+1)个"1"的下标为(5),则(B_3=5)

 0 1 0 1[0] // c数组(省略c[0])

第四次 : (A_2=3),第(3+1)个"1"的下标为(4),则(B_2=4)

 0 1 0[0]0  // c数组(省略c[0])

第五次 : (A_1=0),第(0+1)个"1"的下标为(2),则(B_1=2)

将B数组顺序输出出来即可

至于怎么求第(A_i+1)个"1",就需要使用树状数组维护c数组的前缀和,每次查询时使用二分

代码

// Memory       :704 KB
// Time         :94 MS
// Code Length  :965 B
#include <cstdio>
#include <iostream>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 8005;
int n, a[N], c[N], h[N];

void add(int x) {
    while (x <= n) {
        c[x]--;
        x += lowbit(x);
    }
}

int ask(int x) {
    int ans = 0;
    while (x) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) {
        // 初始化树状数组
        c[i]++;
        if (i + lowbit(i) <= n) c[i + lowbit(i)] += c[i];
    }
    a[1] = 1;  // 本来为0,提前加1
    for (int i = 2; i <= n; i++) {
        scanf("%d", &a[i]); 
        a[i]++; //提前加1
    }
    for (int i = n; i; i--) {
        // 二分
        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (ask(mid) < a[i]) l = mid + 1;
            else r = mid;
        }
        // 记录答案,并更新树状数组
        add(h[i] = l);
    }
    for (int i = 1; i <= n; i++) printf("%d
", h[i]);
    return 0;
}