题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意就是给一个h*w的矩形，往上面放n个高度为1宽度任意的条，优先选择放在左上方，对于每一个条，问放在了第几行。 题目中h给的范围是10^9，但是实际上不需要那么大，n是多少，h最大也就是多少，最多的情况就是一行贴一条，所以h的范围实际上是200000，这样显然就没有那么虐心了。。每一个结点存储的信息就是再该段区间内所有行中所剩的最大的空间（我自己都说不明白了。。），这样一来，对于每一个条询问的时候，首先能知道该区间段内是否能够放得下这个条，如果能放下就往下找，优先找左子树，左子树放不下再找右子树，一直往下递归，最后放下了以后再更新到上面去。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 const int maxn = 200010;
9 int h, w, n;
10 int MAX[maxn << 2];
11 void PushUp(int rt)
12 {
13 MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
14 }
15 void build(int l, int r, int rt)
16 {
17 MAX[rt] = w;
18 if (l == r) return;
19 int m = (l + r) >> 1;
20 build(l, m, rt << 1);
21 build(m + 1, r, rt << 1 | 1);
22 }
23 int query(int x, int l, int r, int rt)
24 {
25 if (l == r)
26 {
27 MAX[rt] -= x;
28 return l;
29 }
30 int m = (l + r) >> 1;
31 int ret = (MAX[rt << 1] >= x) ? query(x, l, m, rt << 1) : query(x, m + 1, r, rt << 1 | 1);
32 PushUp(rt);
33 return ret;
34 }
35 int main()
36 {
37 while (scanf("%d%d%d", &h, &w, &n) != EOF)
38 {
39 if (h > n) h = n;
40 build(1, h, 1);
41 while (n--)
42 {
43 int x;
44 scanf("%d", &x);
45 if (MAX[1] < x) printf("-1\n");
46 else printf("%d\n", query(x, 1, h, 1));
47 }
48 }
49 return 0;
50 }
51
|