題目鏈接：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
|