首页 > 代码库 > poj2828-Buy Tickets
poj2828-Buy Tickets
题目链接 http://vjudge.net/problem/POJ-2828
解题思路
好吧。。。感觉跟Lost Cow那道题好像。。。
然后稀里糊涂地过了。。。3500+ms(时限4s(⊙﹏⊙)b)
线段树。。。单点
代码
#include<stdio.h>#include<string.h>#define MAX_SIZE 200010struct node { int left, right; int num;};struct person { int index; int value;};node tree[4*MAX_SIZE];person que[MAX_SIZE];int ans[MAX_SIZE];void Build(int root, int l, int r){ tree[root].left = l; tree[root].right = r; tree[root].num = r - l + 1; if(l == r) return ; int mid = (l + r) / 2; Build(root*2, l, mid); Build(root*2+1, mid+1, r);}int query(int root, int pos){ tree[root].num--;// int mid = (tree[root].left + tree[root].right) / 2; if(tree[root].left == tree[root].right) { return tree[root].left; } if(pos <= tree[root*2].num) return query(root*2, pos); else return query(root*2+1, pos - tree[root*2].num);}int main(){ int n; while(scanf("%d", &n) == 1) { Build(1, 1, n); for(int i=1; i<=n; i++) { int x, y; scanf("%d%d", &x, &y); que[i].index = x; que[i].value = y; } for(int i=n; i>=1; i--) { int where = query(1, que[i].index+1); ans[where] = que[i].value; } for(int i=1; i<=n; i++) printf(i==n?"%d\n":"%d ", ans[i]); } return 0;}
poj2828-Buy Tickets
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。