POJ2182 Lost Cows

博客图片

题目概述

给出一个从(1-N)这个(N)个数字的前面比它大的数字的个数,输出原始的输入序列.输入首先是(N),然后是(N-1)个整数,表示从第二个数开始,它前面有多少个数字比它大.输入数据规模:

[1leq N leq 8cdot10^3 ]

题目分析

从最后一个元素开始,既然前面比它大的数字有(a[n])个,那么它是(1sim N)中第(pre[n]+1)大的数字,然后用同样的方法可以求出倒数第二个,倒数第三个,(ldots).这里面注意之前已经调出的数字在后面的排序中不应该出现,可以用一个数组标记这个数此前有没有使用,可以在(O(n))的时间确定一个整数,整个程序的时间复杂度为(O(n^2)).

利用树状数组的特性,可以在(O(log(n)))时间内找到剩下的数中的第(pre_i +1)大的数字.树状数组的特性是一个节点可以控制前面几个节点,比如(lowbit(4)=4),表明前面的(tree[1],tree[2],tree[3],tree[4])的改变都可以影响(tree[4]).设定(tree[i]=lowbit(i)),表示数(i)前面的有多少个是改变会影响(tree[i])的值,在初始时而且(sum(i))恰好表示的是(i)是第几个数.当某一个数(k)被取出来后,通过修改(tree[k])的值,确切来说是将(tree[k])减一,然后后面只要被(tree[k])影响的结点的值都会发生改变.

以题目中给出的样例来说,记过初始化后tree:

1	2	3	4	5
1	2	1	4	1

从后向前,查询第一个数,得到的是1,然后把tree[1]减一,然后与tree[1]相关的都会减一,得到

1	2	3	4	5
0	1	1	3	1

然后是计算sum(x)为2的x得到的是3,然后add(3,-1)得到:

1	2	3	4	5
0	1	0	2	1

然后是就散sum(x)为3时的x得到x是4,然后add(4,-1)得到:

1	2	3	4	5
0	1	0	1	1

然后是就散sum(x)为2时的x得到x是5,然后add(5,-1)得到:

1	2	3	4	5
0	1	0	1	0

最后是就是那sum(x)为1时的x得到2,再计算add(2,-1)得到:

1	2	3	4	5
0	0	0	0	0

占坑:一定是糊涂了,没法表述清楚,后面有时间一定更新重写.

代码

/*
 * @Author: Shuo Yang
 * @Date: 2020-08-05 11:41:18
 * @LastEditors: Shuo Yang
 * @LastEditTime: 2020-08-05 12:34:42
 * @FilePath: /Code/2182.cpp
 */
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int pre[N];
int tree[N];
int n;

inline int lowbit(int x){
    return x & -x;
}

void add(int x, int v){
    while(x <= n){
        tree[x] += v;
        x += lowbit(x);
    }
}

int sum(int x){
    int ans = 0;
    while( x > 0){
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}


int binary_find(int v){
    int l = 1;
    int r = n;
    while(l < r){
        int mid = (l + r)/2;
        if( sum(mid) < v){
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    // printf("l=%d
",l);
    return l;
}

int buf[N];

int main(int argc, const char** argv) {
    scanf("%d", &n);
    tree[1] = lowbit(1);
    for(int i = 2; i <= n; ++i){
        scanf("%d",&pre[i]);
        tree[i] = lowbit(i);
    }
    for(int i = n; i > 0;--i){
        int x = binary_find(pre[i]+1);
        // printf("i=%d,x=%d",i,x);
        add(x, -1);
        buf[i] = x;
    }
    for(int i = 1; i <= n; ++i ){
        printf("%d
",buf[i]);
    }
    return 0;
}