hdu 2795 公告板（单点最值）

题意：有个公告板，大小为h*w,要贴n张公告，每个公告的长度是x，高度固定为1，公告放的要尽可能靠上并尽可能靠左，每给出一张公告，要求这个公告在满足要求的情况下放在了第几层。

Sample Input
3 5 5
2
4
3
3
3

Sample Output
1
2
1
3
-1

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # include <queue>
 7 # define LL long long
 8 using namespace std ;
 9 
10 const int maxn = 200010;
11 
12 int MAX[maxn<<2] ; //结点开4倍
13 int h , w , n ;
14 
15 void PushUP(int rt) //更新到父节点
16 {
17     MAX[rt] = max(MAX[rt * 2] , MAX[rt * 2 + 1] ); //rt 为当前结点
18 }
19 
20 void build(int l , int r , int rt) //构建线段树
21 {
22     MAX[rt] = w ;
23     if (l == r)
24     {
25         return ;
26     }
27     int m = (l + r) / 2 ;
28     build(l , m , rt * 2) ;
29     build(m + 1 , r , rt * 2 +1) ;
30 
31 }
32 
33 int query(int x , int l , int r , int rt)  //区间求最大值的位子 直接把update的操作在query里做了
34 {
35     if (l == r)
36     {
37        MAX[rt] -= x ;
38        return l ;    //每个叶子节点代表公告板的行
39     }
40     int m = (l + r) / 2 ;
41     int ret = 0 ;
42     if (MAX[rt * 2] >= x)
43         ret = query(x , l , m , rt * 2) ;
44     else
45         ret = query(x , m+1 , r , rt * 2 + 1) ;
46     PushUP(rt) ;
47     return ret ;
48 }
49 
50 int main ()
51 {
52     //freopen("in.txt","r",stdin) ;
53     while(scanf("%d %d %d" , &h , &w , &n) != EOF)  // h为高 w为宽  n为数量
54     {
55         if (h > n)
56         h = n ;
57         build(1 , h , 1);
58         while (n--)
59         {
60            int x ;
61            scanf("%d" , &x) ;
62            if (x > MAX[1])  //如果一个公告的宽度 比1-h这区间 所有的剩余宽度都大  就是放不下了
63               printf("-1
") ;
64            else
65               printf("%d
" , query(x , 1 , h , 1)) ;
66         }
67     }
68 
69     return 0 ;
70 }

View Code

hdu 2795 公告板 （单点最值）

hdu 2795 公告板（单点最值）