poj 2828 Buy Tickets(动态队列·线段树单点更新)

本文主要是介绍poj 2828 Buy Tickets(动态队列·线段树单点更新)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://poj.org/problem?id=2828

大意：一群人排队，第i个人来到队伍中站到处于posi的人的右边，且每个人都有不同的表示值，问最终的结果？

Sample Input

4
0 77
1 51
1 33
2 69
4
0 20523
1 19243
1 3890
0 31492

Sample Output

77 33 69 51
31492 20523 3890 19243

Hint

能力低，感觉自己还得好好加油啊。。初读这题，感觉很厉害的样子，果然，想了很久还是没得到结果。参考了大神们的思路，总算有点头绪了。正确排序的关键是后来的有位置上的优先权：所以从后向前输入，用一颗二叉树的叶子节点来放各个点。pos决定初始位置，在二叉树中寻找叶子节点即可，如果pos没有空余的位置了就向后放（右子树）。起初我怀疑过这种方法，比如：
考虑从后往前输入，第一个例子：
0 0 69 0
0 33 69 0
0 33 69 51
77 33 69 51
但是第二个例子：
31492  0 0 0
31492 3890 0 0 
31492 3890 19243 0
31492 3890 19243 20523
这不是和结果不符吗？但还好可以进一步用pos和num的关系来决定位置，详见代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;
int ans[maxn];
struct node{int l,r,num;int mid(){  return (l+r)/2; }
}tree[maxn<<2];
void build(int root,int low,int high){tree[root].l=low;tree[root].r=high;if(low==high){tree[root].num=1;return ;}int m=tree[root].mid();build(2*root,low,m);  //no if elsebuild(2*root+1,m+1,high);tree[root].num=tree[2*root].num+tree[2*root+1].num;
}
void insert(int root,int p,int val){if(tree[root].l==tree[root].r){//cout<<tree[root].l<<endl;tree[root].num=0;ans[tree[root].l]=val;return ;}if(p<=tree[2*root].num)insert(2*root,p,val);else  {p=p-tree[2*root].num;  //pos有一个作用：测试num，pos-num变成右子树的测试numinsert(2*root+1,p,val); //eg.p=3,left_num=1,for right_tree: p=2}  //if p=3,left_tree is full,left_num=0, find suitable place in right_tree.tree[root].num=tree[2*root].num+tree[2*root+1].num;
}
struct tnode{int pos,val;
}tp[maxn];
int main()
{//freopen("cin.txt","r",stdin);int n;while(cin>>n){build(1,1,n);for(int i=0;i<n;i++){scanf("%d%d",&tp[i].pos,&tp[i].val);}//for(int i=7;i>=1;i--)cout<<tree[i].num<<" ";  cout<<endl;for(int i=n-1;i>=0;i--){insert(1,tp[i].pos+1,tp[i].val);}//for(int i=7;i>=1;i--)cout<<tree[i].num<<" ";  cout<<endl;for(int i=1;i<n;i++){printf("%d ",ans[i]);}printf("%d\n",ans[n]);}return 0;
}

这篇关于poj 2828 Buy Tickets(动态队列·线段树单点更新)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---