首页 > 代码库 > hdu2795

hdu2795

  题意:有一个h*w的木板,放置一些1*L的物品,将物品尽可能的往上面和左边放置。

  思路:维护一个区间的可以容纳板子长度的最大值

 

  AC代码:

  

 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstdlib> 7  8 using namespace std; 9 10 const int maxn = 200000 + 10;11 12 int h, w, n, x;13 14 struct node15 {16     int l, r, v;17 18 } b[maxn<<2];19 20 void build(int l, int r, int i)21 {22     b[i].l = l;23     b[i].r = r;24     int m = (l + r) >> 1;25     if(l == r) {26         b[i].v = w;27         return ;28     }29     build(l, m, i<<1);30     build(m+1, r, i<<1|1);31     b[i].v = max(b[i<<1].v, b[i<<1|1].v);32 }33 34 int Query(int id, int num, int i)35 {36     int ret;37     if(b[i].l == b[i].r) {38         b[i].v -= num;39         return b[i].l;40     }41     else {42         if(num <= b[i<<1].v) ret = Query(id, num, i<<1);43         else ret = Query(id, num, i<<1|1);44     }45     b[i].v = max(b[i<<1].v, b[i<<1|1].v);46     return ret;47 }48 49 int main()50 {51     //freopen("test.in", "r", stdin);52     while(scanf("%d%d%d", &h, &w, &n) != EOF) {53         int H = min(h, n);54         build(1, H, 1);55         for(int i = 1; i <= n; i++) {56             scanf("%d", &x);57             if(b[1].v < x) puts("-1");58             else printf("%d\n", Query(1, x, 1));59         }60     }61     return 0;62 }
View Code

 

hdu2795