首页 > 代码库 > poj2828--Buy Tickets
poj2828--Buy Tickets
题意 :总共n个人，一个一个的来排队，每个人都有一个要求，要求排到第几个人后面（当然肯定是最后面来的人的要求先满足），每个人有一个对应的val，按顺序输出n的人的val。
用线段树来维护区间剩余的位置数量，，当然必须从最后一个人向前来更新线段树，每次更新之后就把该位置的剩余数量置为0（因为后面的人的要求肯定最先满足嘛）
代码如下：
#include <set>#include <map>#include <cmath>#include <ctime>#include <queue>#include <stack>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef unsigned long long ull;typedef long long ll;const int inf = 0x3f3f3f3f;const double eps = 1e-8;const int maxn = 2e5+10;int seg[maxn<<2],ans[maxn],Pos[maxn],val[maxn],n;void build(int l,int r,int pos){ if (l == r) { seg[pos] = 1; return; } int mid = (l + r) >> 1; build(l,mid,pos<<1); build(mid+1,r,pos<<1|1); seg[pos] = seg[pos<<1] + seg[pos<<1|1];}int update(int l,int r,int pos,int x){ if (l == r) { seg[pos] = 0; return l; } int mid = (l + r) >> 1; int ans; if (seg[pos<<1] >= x) ans = update(l,mid,pos<<1,x); else ans = update(mid+1,r,pos<<1|1,x-seg[pos<<1]); seg[pos] = seg[pos<<1|1] + seg[pos<<1]; return ans;}int main(void){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif while (~scanf ("%d",&n)) { for (int i = 0; i < n; i++) { scanf ("%d%d",Pos+i,val+i); } build(1,n,1); for (int i = n - 1; i >= 0; i--) { int tmp = update(1,n,1,Pos[i]+1); ans[tmp-1] = val[i]; } printf("%d",ans[0]); for (int i = 1; i < n; i++) { printf(" %d",ans[i]); } printf("\n"); } return 0;}
poj2828--Buy Tickets
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。