poj 2828 Buy Tickets

Description Input Output Sample Input Sample Output 这道题目想法很重要，先建树，每个节点表示这个区间内的空的位置的数量，然后，从后往前读，Pos的值表示这个人前面有多少个空位，之所以从后往前读，是因为这样每个人的位置是确定的，以后就不用移动了，以后直接在树里面查找空位就可以了。 具体实现见代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int maxn = 222222;
int tree[maxn<<2], val[maxn], pos[maxn], ans[maxn];
int id;
void build(int l, int r, int rt){
  tree[rt] = r - l + 1;
  if (l == r) {return;}
  int m = (l + r) >> 1; build(lson); build(rson);
}
void update(int p, int l, int r, int rt){
  tree[rt]--;
  if (l == r){id = l-1; return;}
  int m = (l + r) >> 1; if (tree[rt<<1] >= p) update(p, lson);
  else {p -= tree[rt<<1]; update(p, rson);}
}
int main(void){
  int n; 
#ifndef ONLINE_JUDGE
  freopen("poj2828.in", "r", stdin);
#endif
  while (~scanf("%d", &n)){
    build(1, n, 1);
    for (int i = 0; i < n; ++i) { scanf("%d%d", pos+i, val+i); }
    for (int i = n - 1; i >= 0; --i){
      update(pos[i] + 1, 1, n, 1);
      ans[id] = val[i];
    }
    for (int i = 0; i < n; ++i){
      if (i == 0) printf("%d", ans[i]);
      else printf(" %d", ans[i]);
    }
    printf("\n");
  }
  return 0;
}

注意这种比较巧妙的想法。做这道题目的时候，我竟然把输入文件写错了，导致测试数据错误，然而，过分的是，我没看出来，然后就华丽丽地交了，然后就过了……糗大了……