POJ 2828 Buy Tickets

发布时间:2017-2-24 21:03:42 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 2828 Buy Tickets",主要涉及到POJ 2828 Buy Tickets方面的内容,对于POJ 2828 Buy Tickets感兴趣的同学可以参考一下。

线段树第二题,变简单了呢,单点更新的~~~ 题目大意: 有一个空队列,给出按时间顺序插队的序列,问最后这个队列里的人按什么顺序排列的。 解题思路: 线段树来做的,每个节点代表着这个节点下还有多少个空位,然后倒叙插入。更新寻找位置。 下面是代码: #include <stdio.h> const int Max=200005; int node[Max<<2],num[Max]; struct node1 { int p,v; } po[Max]; void build(int l,int r,int tr) { node[tr]=r-l+1; if(l==r)return; int m=(l+r)>>1; build(l,m,tr<<1); build(m+1,r,tr<<1|1); } int query(int p,int l,int r,int tr) { node[tr]--; if(l==r)return l; int m=(l+r)>>1; if(node[tr<<1]>=p)return query(p,l,m,tr<<1); else return query(p-node[tr<<1],m+1,r,tr<<1|1); } int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=0; i<n; i++) { scanf("%d%d",&po[i].p,&po[i].v); } build(1,n,1); for(int i=n-1; i>=0; i--) { num[query(po[i].p+1,1,n,1)]=po[i].v; } for(int i=1; i<n; i++) { printf("%d ",num[i]); } printf("%d\n",num[n]); } return 0; }

上一篇:漫谈 Clustering (4): Spectral Clustering
下一篇:Oracle自增序列号

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。