(资料图)
传送门
题目描述
有 \(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;} 
