題目鏈接：http://poj.org/problem?id=2828 題目一看好高深啊 ，不過(guò)還好，AC。。 這道題如果正著看，那么每一個(gè)人的地方都有可能變動(dòng)，但是如果倒著看，每一個(gè)只要入隊(duì)了，他的位置就不再改變，這樣的話就是一道赤裸裸的線段樹(shù)單點(diǎn)更新了，每一個(gè)結(jié)點(diǎn)存儲(chǔ)的是該區(qū)間內(nèi)還有多少個(gè)空位，每一次遇到一個(gè)人的時(shí)候，都把他插入到正確的位置，至于怎么算正確的位置，如果當(dāng)前結(jié)點(diǎn)左子樹(shù)權(quán)值大于pos，那么就往左邊放，否則就往右邊放，放不進(jìn)去左邊的時(shí)候，pos要減去左邊的空位數(shù)，否則的話有可能右邊也放不進(jìn)去，最后根本放不到葉子結(jié)點(diǎn)里面。每進(jìn)入一個(gè)區(qū)間，該區(qū)間的空位數(shù)就減少一個(gè)，這個(gè)千萬(wàn)不要忘了處理。最后用一個(gè)數(shù)組來(lái)存儲(chǔ)插入進(jìn)去以后的最終位置。
  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
|