HDU 2795 Billboard

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=2795

题意：h*w的空间，给出1*L的木板，要求放在最高层且能放进的位置，最高层为1，最底层为h。

思路：线段树算法。每个节点存储的值sum[rt]为当前区间的最大宽度。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define inf 0x7fffffff
 7 using namespace std;
 8 
 9 const int maxn=200000+10;
10 int sum[maxn*4];
11 int h,w,n,x;
12 void PushUP(int rt)
13 {
14     sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
15 }
16 void build(int l,int r,int rt,int x)
17 {
18     sum[rt]=x;
19     if (l==r) return ;
20     int m=(l+r)>>1;
21     build(l,m,rt<<1,x);
22     build(m+1,r,rt<<1|1,x);
23 }
24 int query(int l,int r,int rt,int x)
25 {
26     if (l==r) {sum[rt] -= x ; return l; }
27     int m=(l+r)>>1;
28     int ret= (sum[rt<<1]>=x) ? query(l,m,rt<<1,x) : query(m+1,r,rt<<1|1,x);
29     PushUP(rt);
30     return ret;
31 }
32 int main()
33 {
34     while (cin>>h>>w>>n)
35     {
36         if (h>n) h=n;
37         build(1,h,1,w);
38         while (n--)
39         {
40             scanf("%d",&x);
41             if (sum[1]<x) printf("-1
");
42             else printf("%d
",query(1,h,1,x));
43         }
44     }
45     return 0;
46 }