POJ2182 Lost Cows

　　线段树。

　　从后往前寻找，首先是找第a[n]大的数，找到后记录到答案数组里并删除改叶子节点，然后在剩下的数字中再找a[n - 1]大的数，直到n次寻找完成。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define lson (cur << 1)
 4 #define rson (cur << 1 | 1)
 5 #define INF 0x3f3f3f3f
 6 #define N 8005
 7 
 8 int a[N], ans[N];
 9 
10 struct node
11 {
12     int l, r;
13     int len;
14     int v;
15 }tree[N << 2];
16 
17 void pushup(int cur)
18 {
19     tree[cur].len = tree[lson].len + tree[rson].len;
20 }
21 
22 void query(int cur, int cnt, int loc)
23 {
24     if(tree[cur].l == tree[cur].r)
25     {
26         ans[loc] = tree[cur].v;
27         tree[cur].len = 0;
28         return ;
29     }
30     if(tree[lson].len >= cnt)
31         query(lson, cnt, loc);
32     else
33         query(rson, cnt - tree[lson].len, loc);
34     pushup(cur);
35 }
36 
37 void build(int cur, int l, int r)
38 {
39     tree[cur].l = l, tree[cur].r = r;
40     if(l == r)
41     {
42         tree[cur].v = l;
43         tree[cur].len = 1;
44         return ;
45     }
46     int mid = (l + r) >> 1;
47     build(lson, l, mid);
48     build(rson, mid + 1, r);
49     pushup(cur);
50 }
51 
52 int main()
53 {
54     int n, i;
55     scanf("%d", &n);
56     build(1, 1, n);
57     a[1] = 1; 
58     for(i = 2; i <= n; i ++)
59     {
60         scanf("%d", &a[i]);
61         a[i] ++;
62     }
63     for(i = n; i >= 1; i --)
64     {
65         query(1, a[i], i);
66     }
67     for(i = 1; i <= n; i ++)
68     {
69         printf("%d\n", ans[i]);
70     }
71     return 0;
72 }