AcWing 244. 谜一样的牛
原题链接
简单
作者:
郡呈
,
2020-06-02 14:33:59
,
所有人可见
,
阅读 688
/*
--------------------
h[N]-牛高
ans[N]-记录答案
tr[N]-线段树存储
--------------------
int lowbit(int x);
void add(int x, int c);
int sum(int x);
---------------------
1.从剩余的数中找到第k小的数~找到一个最大的x使得k==sum(x)
2.删除某个数
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int h[N], res[N], tr[N];
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; i -= lowbit(i)) res += tr[i];
return res;
}
int main() {
cin >> n;
for(int i = 2; i <= n; i++) cin >> h[i];
for(int i = 1; i <= n ;i++) tr[i] = lowbit(i);
for(int i = n; i; i--) {
int k = h[i] + 1;
int l = 1, r = n;
while(l < r) {
int mid = l + r >> 1;
if(sum(mid) >= k) r = mid;
else l = mid + 1;
}
res[i] = r;
add(r, -1);
}
for(int i = 1; i <= n; i++) cout << res[i] << endl;
return 0;
}