题目链接：http://poj.org/problem?id=2828 题目一看好高深啊 ，不过还好，AC。。 这道题如果正着看，那么每一个人的地方都有可能变动，但是如果倒着看，每一个只要入队了，他的位置就不再改变，这样的话就是一道赤裸裸的线段树单点更新了，每一个结点存储的是该区间内还有多少个空位，每一次遇到一个人的时候，都把他插入到正确的位置，至于怎么算正确的位置，如果当前结点左子树权值大于pos，那么就往左边放，否则就往右边放，放不进去左边的时候，pos要减去左边的空位数，否则的话有可能右边也放不进去，最后根本放不到叶子结点里面。每进入一个区间，该区间的空位数就减少一个，这个千万不要忘了处理。最后用一个数组来存储插入进去以后的最终位置。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 200010;
11 int sum[maxn << 2], pos[maxn], val[maxn], ans[maxn], id;
12 void PushUp(int rt)
13 {
14 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
15 }
16 void build(int l, int r, int rt)
17 {
18 if (l == r)
19 {
20 sum[rt] = 1;
21 return;
22 }
23 int m = (l + r) >> 1;
24 build(lson);
25 build(rson);
26 PushUp(rt);
27 }
28 void query(int p, int l, int r, int rt)
29 {
30 sum[rt]--;
31 if (l == r)
32 {
33 id = l;
34 return;
35 }
36 int m = (l + r) >> 1;
37 if (p <= sum[rt << 1]) query(p, lson);
38 else
39 {
40 p -= sum[rt << 1];
41 query(p, rson);
42 }
43 }
44 int main()
45 {
46 int n;
47 while (scanf("%d", &n) != EOF)
48 {
49 build(1, n, 1);
50 for (int i = 1; i <= n; i++) scanf("%d%d", &pos[i], &val[i]);
51 for (int i = n; i >= 1; i--)
52 {
53 query(pos[i] + 1, 1, n, 1);
54 ans[id] = val[i];
55 }
56 for (int i = 1; i <= n; i++)
57 {
58 printf("%d", ans[i]);
59 if (i == n) printf("\n");
60 else printf(" ");
61 }
62 }
63 return 0;
64
|