Loading... # ACWing 244 谜一样的牛 题解 ## 题目描述 有$n$头奶牛，已知它们的身高为$1∼n$且各不相同，但不知道每头奶牛的具体身高。 现在这$n$头奶牛站成一列，已知第$i$头牛前面有$A_i$头牛比它低，求每头奶牛的身高。 ## 输入 第$1$行：输入整数$n$。 第 $2\cdots n$行：每行输入一个整数$A_i$，第$i$行表示第$i$头牛前面有$A_i$头牛比它低。 （注意：因为第$1$头牛前面没有牛，所以并没有将它列出） ## 输出 输出包含$n$行，每行输出一个整数表示牛的身高。 第$i$行输出第$i$头牛的身高。 ## 样例 ### 输入 ``` 5 1 2 1 0 ``` ### 输出 ``` 2 4 5 3 1 ``` ## 解题思路 不难发现， 从前向后很难确定牛的身高， 但是不难发现， 对于最后一个元素$0$， 代表前面没有任何牛比他矮， 又因为当前未排序的牛的数量为$5$头， 因此最后一头牛的身高为$1$ 确定最后一头牛后， 此时牛的数量为$4$， 而倒数第二头牛前面有一头牛比他矮， 因此倒数第二头牛的身高为$3$ 为了处理这个问题， 我们可以维护这样一个数组`a`，`a[i]`表示前`i` 头牛中未被选中的牛的头数， 则上述过程可以简化为如下的表格， 由于队头的牛一定没有比他矮的站在他前面， 因此为$0$ | 输入 | 1号牛 | 2号牛 | 3号牛 | 4号牛 | 5号牛 | | ---- | ------- | ------- | ------- | ------- | ------- | | 0 | 1(选中) | 2 | 3 | 4 | 5 | | 1 | 0 | 1 | 2(选中) | 3 | 4 | | 2 | 0 | 1 | 1 | 2 | 3(选中) | | 1 | 0 | 1 | 1 | 2(选中) | 2 | | 0 | 0 | 1(选中) | 1 | 1 | 1 | 可以发现， 我们要维护的数组`a`是一个前缀和数组， 这个数组支持插入和单点修改操作， 同时数组还具有单调上升的性质， 因此可以考虑通过树状数组+二分的方式解决这个问题。 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 2e5 + 10; int n; int a[N]; int tr[N]; vector<int> ans; int lowbit(int x) { return x & -x; } void add(int x, int c) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; } int sum(int x) { int res = 0; for(int i = x; i > 0; i -= lowbit(i)) res += tr[i]; return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i ++) { if(i != 1) cin >> a[i]; add(i, 1); } for(int i = n; i >= 1; i --) { int x = a[i]; int l = 1, r = n; while(l < r) { int mid = l + r >> 1; if(sum(mid) > x) r = mid; else l = mid + 1; } ans.push_back(l); add(l, -1); } for(int i = ans.size() - 1; i >= 0; i --) cout << ans[i] << endl; return 0; } ``` 最后修改：2025 年 04 月 17 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏