本文主要是介绍线段树--poj2828 Buy tickets，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一开始为空队列，n个人，每次插队在第p个人后面，求最后的位置。
当最后一个人插入时，他的位置与最后的结果中的位置相同，可确定，所以倒着求。
用线段树记录区间内空格数。
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 200000 + 5;
int seg[maxn << 2];
int val[maxn],pos[maxn],ans[maxn];
void init(int l,int r,int rt)
{
if (l == r) {
seg[rt] = 1;
return;
}
int mid = (l + r) >> 1;
init(l, mid, rt << 1);
init(mid + 1, r, rt << 1 | 1);
seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}
void update(int l,int r,int rt,int val,int pos)
{
if (l == r) {
seg[rt] = 0;
ans[l] = val;
return ;
}
int mid = (l + r) >> 1;
if (seg[rt << 1] >= pos) {
update(l, mid,rt << 1 , val, pos);
}
else update(mid + 1, r, rt << 1 | 1, val, pos - seg[rt << 1]);
seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}
int main()
{
int n;
while (scanf("%d",&n) != EOF && n) {
init(1, n, 1);
for (int i = 0; i < n; i ++) {
scanf("%d%d",&pos[i],&val[i]);
}
for (int i = n - 1; i >= 0; i --) {
update(1, n, 1, val[i], pos[i] + 1 );
}
for (int i = 1; i <= n; i ++) {
printf("%d",ans[i]);
if (i == n) {
printf("\n");
}
else printf(" ");
}
}
return 0;
}
这篇关于线段树--poj2828 Buy tickets的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
