244. 谜一样的牛（树状数组）

偏执的太偏执、 2021-11-11 18:42 223阅读 0赞

题目链接：[https://www.acwing.com/problem/content/245/][https_www.acwing.com_problem_content_245]  
有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。

现在这n头奶牛站成一列，已知第i头牛前面有Ai

头牛比它低，求每头奶牛的身高。  
输入格式

第1行：输入整数n。

第2…n行：每行输入一个整数Ai  
,第i行表示第i头牛前面有Ai

头牛比它低。  
（注意：因为第1头牛前面没有牛，所以并没有将它列出）  
输出格式

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

第i行输出第i头牛的身高。  
数据范围

1≤n≤105

输入样例：

5  
1  
2  
1  
0

输出样例：

2  
4  
5  
3  
1

分析:  
在分析的时候，明确自己需要啥。然后，在不断模拟的过程中，找到更简便的方法，达到自己的目的。  
这个题，我一波错误分析，wa飞了。xuxuxu

看到题目。很自然而然的相到从后面往前找。因为最后一个的身高一定为  
h\[N\] = a\[N\] + 1.  
那么前一个的身高为多少呢？  
h\[N-1\] = a\[N-1\] + 1 （if（a\[N -1\] < a\[N\]） 或者  
h\[N-1\] = a\[N-1\] + 2 （if ( a\[N -1\] >= a\[N\]）  
这是容易得到的。  
所以，我们  
对于每个h\[i\] = a\[i\] + 1 + x.我就是因为这里想错了。我一开始想的是对于每个a\[i\]求一下他之前出现的个数有多少个。但是后面发现这并不行。

其实，我们由h\[N-1\]可以得到另外一个思想：  
对于每个h\[i\] 是不是在（1-N）这个序列（这个序列不包括已经安排了的身高）中找到第a\[i\] + 1大的那个数就好了呢。  
故，我们的目的现在变成了，对于每个h\[i\] 在序列（1-N）中找到未出现过的身高的第a\[i\]+1大的值就可以了。  
为了达到这个目的，通俗的想便是遍历一次序列找到那个值。但是这样很明显超时。  
那么我们用一个C数组。C\[i\] 表示前i个数有多少个数是未被使用过的，这样是可以的。  
然后，我们便可以用二分或者倍增的方法求出第a\[i\] + 1大的那个数了。  
如果i这个数被使用了，则要修改C数组。这不就是树状数组的单点修改吗。

明确目的，通过方法解决目的。开展思维，证明可行性。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int N,a[100100];
    int C[100010];
    int h[100010];
    int id[100010];
    int S;
    
    int lowbit(int x)
    {
        return x & (-x);
    }
    
    void add(int x,int v)
    {
        while(x <= N) { C[x] += v; x += lowbit(x); }
    }
    
    int ask(int x)
    {
        int sum = 0;
        while(x > 0)
        {
            sum += C[x]; x -= lowbit(x);
        }
        return sum;
    }
    
    int main()
    {
        scanf("%d",&N);
        S = 1;
        add(1,1);
        for(int i = 2; i <= N; i ++)
        {
            scanf("%d",&a[i]);
            add(i,1);
            S += i;
        }
        for(int i = N; i >= 2; i --)
        {
            int ans = a[i] + 1;
            int  l = 1,r = N;
            while(l < r)
            {
                int mid = (l + r) >> 1;
                int cont = ask(mid);
                if(cont < ans)
                    l = mid + 1;
                else
                    r = mid;
            }
            h[i] = l;
            add(l,-1);
            S -= l;
        }
        h[1] = S;
        for(int i = 1; i <= N; i ++)
            printf("%d\n",h[i]);
    }

[https_www.acwing.com_problem_content_245]: https://www.acwing.com/problem/content/245/