POJ2182 Lost Cows

傷城~ 2023-03-06 05:40 21阅读 0赞

# POJ2182 Lost Cows #

![博客图片][format_png]

## 题目概述 ##

[POJ2182 Lost Cows][]

## 题目概述 ##

给出一个从 1 − N 1-N 1−N这个 N N N个数字的前面比它大的数字的个数,输出原始的输入序列.输入首先是 N N N,然后是 N − 1 N-1 N−1个整数,表示从第二个数开始,它前面有多少个数字比它大.输入数据规模:  
 1 ≤ N ≤ 8 ⋅ 1 0 3 1\\leq N \\leq 8\\cdot10^3 1≤N≤8⋅103

## 题目分析 ##

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

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

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

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

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

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

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

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

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

## 代码 ##

/*
     * @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\n",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\n",buf[i]);
        }
        return 0;
    }

## 其它 ##

[format_png]: /images/20230208/30eb0947ba9948b5b9e70f801f2847ff.png
[POJ2182 Lost Cows]: http://poj.org/problem?id=2182