首页 > 代码库 > 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 }
hdu2795
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。