首页 > 代码库 > 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