欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj 2182 Lost Cows

程序员文章站 2024-03-02 21:59:22
...

题目链接

题目大意:

有n头奶牛,已知它们的身高为 1~n 且各不相同,但不知道每头奶牛的具体身高。现在这n头奶牛站成一列,已知第i头牛前面有Ai头牛比它低,求每头奶牛的身高。

思路

从最后一头牛考虑,如果最后一头牛前面有a个比它小的,那么可以肯定最后一头牛的身高就是a + 1,也就是序列中未被访问的第 a + 1个,对于最后一头牛,因为一开始所有的身高都存在,都没有被某一头牛占领(没有确定),因此就是a + 1了。

对于倒数第二个,在确定完最后一头牛后,倒数第二个现在成了最后一个,那么对应的就是在现在的身高集合(上一个集合减去了刚刚被确定的牛的身高)中的第a + 1大的数,因此可以采用树状数组维护一个数组C,C数组维护的是当前的数字前面(包含当前)有多少个数字没有被确定,初始化的时候调用add函数初始化,对于每一次查询的话,可以采用二分的策略。

对于当前传递进来的第a + 1个,二分上下限为1和n,每次判断mid出查询出来的前缀和是否大于等于a + 1,如果满足条件,则缩小上限,否则缩小下限,二分出来的结果就是答案,最后将答案倒叙输出即可。

#include <cstdio>
#include <cstring>
#define mem(a, b) memset(a, b, sizeof a)
#pragma warning (disable:4996)
#pragma warning (disable:6031)
#define debug(i, j) printf("query(%d) = %d;\n", i, j)
const int N = 110000;
using namespace std;
int c[N];
int n;
int a[N];
int res[N];
int lowbit(int x) {
	return x & -x;
}
void add(int x, int val) {
	while (x <= n) {
		c[x] += val;
		x += lowbit(x);
	}
}
int	query(int x) {
	int res = 0;
	while (x) {
		res += c[x];
		x -= lowbit(x);
	}
	return res;
}
int lower_bound(int val) {
	int l = 1;
	int r = n;
	int res = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (query(mid) >= val) {
			res = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	return res;
}
int main()
{
	while (~scanf("%d", &n)) {
		mem(a, 0);
		mem(c, 0);
		for (int i = 1; i <= n; i++)add(i, 1);
		a[1] = 0;
		for (int i = 2; i <= n; i++)scanf("%d", a + i);

		for (int i = n; i > 0; i--) {
			int ind = lower_bound(a[i] + 1);
			res[i] = ind;
			add(ind, -1);
		}
		for (int i = 1; i <= n; i++) {
			printf("%d\n", res[i]);
		}
	}
	return 0;
}

代码: