題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2795 題意就是給一個h*w的矩形，往上面放n個高度為1寬度任意的條，優(yōu)先選擇放在左上方，對于每一個條，問放在了第幾行。 題目中h給的范圍是10^9，但是實(shí)際上不需要那么大，n是多少，h最大也就是多少，最多的情況就是一行貼一條，所以h的范圍實(shí)際上是200000，這樣顯然就沒有那么虐心了。。每一個結(jié)點(diǎn)存儲的信息就是再該段區(qū)間內(nèi)所有行中所剩的最大的空間（我自己都說不明白了。。），這樣一來，對于每一個條詢問的時候，首先能知道該區(qū)間段內(nèi)是否能夠放得下這個條，如果能放下就往下找，優(yōu)先找左子樹，左子樹放不下再找右子樹，一直往下遞歸，最后放下了以后再更新到上面去。
  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
|