POJ 2182-Lost Cows【树状数组+二分】

秒速五厘米 2023-10-09 11:55 20阅读 0赞

有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。

现在这n头奶牛站成一列，已知第i头牛前面有AiAi头牛比它低，求每头奶牛的身高。

输入格式

第1行：输入整数n。

第2..n行：每行输入一个整数AiAi,第i行表示第i头牛前面有AiAi头牛比它低。  
（注意：因为第1头牛前面没有牛，所以并没有将它列出）

输出格式

输出包含n行，每行输出一个整数表示牛的身高。

第i行输出第i头牛的身高。

数据范围

1≤n≤105

思路：从后往前考虑每头牛，对于Hn = an + 1, 那么对于第n-1头牛，如果an-1 < an, 那么Hn = an-1 + 1  ，否则Hn = an-1 + 2

也就是相当于在\[1, n\]中找到第ai + 1个没有出现过的位置。

我们先将位置序列都设为1，如果出现了就改为0，利用树状数组可以方便的求得，另外可以通过二分答案使其每次操作的复杂度

降为logn \* logn

#include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 1e5 + 10;
    const int mod = 1e9 + 7;
    int a[maxn], c[maxn], p[maxn];
    int n;
    
    int lowbit(int x)
    {
        return (x & (-x));
    }
    void add(int i, int x)
    {
        while(i < maxn)
        {
            c[i] += x;
            i += lowbit(i);
        }
    }
    int ask(int i)
    {
        int ret = 0;
        while(i > 0)
        {
            ret += c[i];
            i -= lowbit(i);
        }
        return ret;
    }
    
    int main()
    {
        scanf("%d", &n);
        for(int i = 2; i <= n; ++i)
            scanf("%d", &a[i]);
        for(int i = 1; i <= n; ++i)
            add(i, 1);
        for(int i = n; i >= 1; --i)
        {
            int x = a[i] + 1;
            int l = 1, r = n;
            while(l <= r)
            {
                if(ask(mid) >= x)
                    p[i] = mid, r = mid - 1;
                else
                    l = mid + 1;
            }
            add(p[i], -1);
        }
        for(int i = 1; i <= n; ++i)
            printf("%d\n", p[i]);
        return 0;
    }