全球看热讯：AcWing244.谜一样的牛

2022-12-26 13:08:35 来源：博客园

(资料图)

传送门

题目描述

有 \(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 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!}\)

关键词：的目标是各不相同我们需要