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;
}
代码:
上一篇: Sqlalchemy 使用总结
下一篇: SQLAlchemy 使用总结