hdu 2795 Billboard

随着对线段树的认识，我的重点放在了，这个线段树里每个元素所代表的意义上了。

这道题我们把每一层看作一个空间，随着往里面放广告，空间越来越小，而线段树所标示的意义就是剩余空间，通过像二分一样的去查找，将时间按复杂度降下来。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MAXN 220000
 4 
 5 int h, w, n, D, tree[MAXN<<2];
 6 int max(int a, int b)
 7 {
 8     if(a > b) return a;
 9     else return b;
10 }
11 int min(int a, int b)
12 {
13     if(a > b) return b;
14     else return a;
15 }
16 
17 void build(int flag)
18 {
19     for(D = 1; D < flag+2; D <<= 1);
20     memset(tree, -1, sizeof(tree));
21     for(int i = 1; i <= flag; i ++)
22         tree[D+i] = w;
23     for(int i = D-1; i > 0; i --)
24         tree[i] = max(tree[i<<1], tree[i<<1|1]);
25 }
26 
27 void query(int x, int cur)
28 {
29     for(;;)
30     {
31         if((cur<<1) > D+min(h, n)) break;
32         if(tree[cur<<1] >= x) cur <<= 1;
33         else cur = (cur<<1|1);
34     }
35     tree[cur] -= x; 
36     for(int i = cur; i^1; i >>= 1)
37         tree[i>>1] = max(tree[i], tree[i^1]);
38     printf("%d\n",cur-D);
39 }
40 
41 void init()
42 {
43     while(~scanf("%d%d%d",&h, &w, &n))
44     {
45         if(h < n) build(h);
46         else build(n);
47         for(int i = 0; i < n; i ++)
48         {
49             int a;
50             scanf("%d",&a);
51             if(tree[1] < a) printf("-1\n");
52             else 
53                 query(a, 1);
54         }
55     }    
56 }
57 
58 int main()
59 {
60     init();
61     return 0;
62 }