本文主要是介绍POJ Buy Tickets，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目分析：
给你N个人的队列，每个人都有想站的位置，要你从前往后的给他们排序，输出最后的结果。注意，后面的人会覆盖前面的。就是是原本在该位置上的人往后移动一个位置。
算法分析：
我们可以把总人数当作区间的大小，然后结果就是把区间的每一个位置都放上人，就是答案了。
而从题目中我们可以知道，后面的人是不受前面的人的影响的。所以，我们可以倒这来模拟过程。
如何模拟呢？我们可以想到用线段树（谁想到的？反正我没想到），根据线段树的特点，我们可以给每个区间的值赋值为该区间还有多少个可用的位置。这样就可以达到了快速查找。
其实，本题的关键就是，会不会想到用线段树的时候，把区间的值赋值为该区间还可用的位置个数。如果，想到了，那么线段树就是很基础了。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;#define L(x) (x << 1)
#define R(x) (x << 1|1)
#define MOD(a,b) (a+((b-a) >> 1))
#define lson lft,md,rt << 1
#define rson md+1,rht,rt << 1|1const int MAXN = 200000 + 10;
struct Node{int lft,rht,val;int mid(){return MOD(lft,rht);}
};Node tree[4*MAXN];
int n,ran[MAXN],num[MAXN],res[MAXN];class SegTree{
public:void Build(int lft,int rht,int rt){tree[rt].lft = lft; tree[rt].rht = rht;tree[rt].val = rht - lft + 1;if(lft != rht){int md = tree[rt].mid();Build(lson);Build(rson);}}int Query(int val,int rt){int lft = tree[rt].lft,rht = tree[rt].rht;if(lft == rht){tree[rt].val = 0;return lft;}else{int pos;if(val <= tree[L(rt)].val)pos = Query(val,L(rt));else pos = Query(val-tree[L(rt)].val,R(rt));tree[rt].val = tree[L(rt)].val + tree[R(rt)].val;return pos;}}
};
int main()
{while(~scanf("%d",&n)){SegTree seg;seg.Build(0,n-1,1);for(int i = 0;i < n;++i){scanf("%d%d",&ran[i],&num[i]);}int pos;for(int i = n-1;i >= 0;--i){pos = seg.Query(ran[i]+1,1); res[pos] = num[i];}for(int i = 0;i < n-1;++i)printf("%d ",res[i]);printf("%d\n",res[n-1]);}return 0;
}这篇关于POJ Buy Tickets的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
