文章

25

粉丝

0

获赞

0

访问

244799

头像
树状数组+二分
经验总结
发布于2020年4月21日 00:23
阅读数 9506

有n头奶牛,已知它们的身高为 1~n 且各不相同,但不知道每头奶牛的具体身高。

现在这nn头奶牛站成一列,已知第i头牛前面有AiAi头牛比它低,求每头奶牛的身高。

输入格式
第1行:输入整数nn。

第2..n行:每行输入一个整数AiAi,第i行表示第i头牛前面有AiAi头牛比它低。
(注意:因为第1头牛前面没有牛,所以并没有将它列出)

输出格式
输出包含nn行,每行输出一个整数表示牛的身高。

第ii行输出第ii头牛的身高。

二分:


int search(int l,int r){
	while (l < r){
		int mid = l + r >> 1;
		if (check(mid) < a[i] + 1){
			l = mid + 1;
		}
		else{
			r = mid;
		}
	}
	return l;
}
#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int n;
int c[N], a[N], ans[N];//ans[N]记录牛的高度
int lowbit(int x){
	return x&(-x);
}
void add(int x, int y){
	for (int i = x; i <= n; i += lowbit(i)){
		c[i] += y;
	}
}
int ask(int x){
	int res = 0;
	for (int i = x; i; i -= lowbit(i)){
		res += c[i];
	}
	return res;
}
int main(){
	cin >> n;
	add(1, 1);
	for (int i = 2; i <= n; i++){
		cin >> a[i];
		add(i, 1);
	}
	for (int i = n; i >= 1; i--){
		int l = 1, r = n;
		while (l < r){
			int mid = l + r >> 1;
			if (ask(mid) < a[i] + 1){
				l = mid + 1;
			}
			else{
				r = mid;
			}
		}
		ans[i] = r;
		add(r, -1);
	}
	for (int i = 1; i <= n; i++){
		cout << ans[i] << endl;
	}

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发