标签：AcWing244 奶牛 头牛 前面 谜一样 int add 身高

传送门

题目描述

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

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

解题思路

\(\qquad\)我们对于这题可以从后向前扫描，当扫描到第i头牛的时候，它前面有a[i]头牛比它低，这说明它的身高在前面i头牛里面排名第a[i]+1名。
\(\qquad\)在前i头牛里身高排名第a[i]+1名又可以转化为在前i-1头牛中，有a[i]头比它低，在逆序对的计算中，我们已经明确了如何正序遍历求出一个数的前面有多少数比它小，由于我们从右向左扫描，所以我们需要略微改动下代码，也是类似桶排的思路，用过之后代表这个数以后不能再选了，所以是add(i, -1)
\(\qquad\)然后就是二分了，二分的目标是排名第k的数，那\(check\)函数就是判断前面是否有>=k个数比它小或者和它相等，我们求的目标是满足\(check\)函数的最小值，也就是前面刚好有k个数和它相等或者比它小，那么这个数也就是排名第\(k\)的数了，我们也就可以得出代码

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int tr[N], n, h[N], ans[N];

void add(int x, int v) 
{
    for (; x <= n; x += x & -x) tr[x] += v;
}

int ask(int x) 
{
    int res = 0;
    for (; x; x -= x & -x) res += tr[x];
    return res;
}

int main() 
{
    scanf("%d", &n);
    
    for (int i = 2; i <= n; i ++ ) 
        scanf("%d", &h[i]);
        
    for (int i = 1; i <= n; i ++ ) add(i, 1);
        
    for (int i = n; i; i -- ) 
    {
        int k = h[i] + 1;
        int l = 0, r = n + 1;
        while (l < r) 
        {
            int mid = l + r >> 1;
            if (ask(mid) >= k) r = mid;
            else l = mid + 1;
        }
        ans[i] = r, add(l, -1);
    }
    
    for (int i = 1; i <= n; i ++ ) 
        printf("%d\n", ans[i]);
        
    return 0;
}

\(\color{Green}{顺利AC!}\)

标签：AcWing244,奶牛,头牛,前面,谜一样,int,add,身高
From： https://www.cnblogs.com/StkOvflow/p/17005525.html