HDU2795 Billboard http://acm.hdu.edu.cn/showproblem.php?pid=2795
线段树例题解析合集 https://www.cnblogs.com/whx666/p/12037809.html
题意: 有一个 h 行 w 列的矩形, 在里面横放 m 条大小为 1*l[i] 的小长方形, 不能重叠, 如果能放得下, 输出能放下的最小行数, 放不下输出 - 1
由于只有 m 个长方形, 最多只需要 m 行 (h 范围很大), 把 h 对 m 取 min
然后维护每行剩下的值的区间最大值, 查询时若左子树代表区间内的最大值 > 需要的长度, 向左子树递归, 否则考虑右子树, 若长度都不够, 答案为 - 1
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 2e5 + 10;
- inline void read (int &x) {
- char ch = getchar(); x = 0;
- while (!isdigit(ch)) ch = getchar();
- while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
- }
- inline int print (int x) {
- if (x <0) putchar ('-'), x = -x;
- if (x> 9) print (x / 10);
- putchar (x % 10 + 48);
- }
- int h, w, n, val, c[N <<2];
- #define ls p << 1
- #define rs p << 1 | 1
- inline int Max (int a, int b) {return a> b ? a : b;}
- int query (int p, int l, int r, int val) {
- if (l == r) {
- if (c[p]>= val) {c[p] -= val; return l;}
- else return -1;
- }
- int mid (l + r>> 1), ans (-1);
- if (c[ls]>= val) ans = query (ls, l, mid, val);
- else if (c[rs]>= val) ans = query (rs, mid + 1, r, val);
- c[p] = Max (c[ls], c[rs]);
- return ans;
- }
- int main() {
- while (~scanf ("%d %d %d", &h, &w, &n)) {
- if (n <h) h = n;
- for (int i = 1; i <= (h << 2); ++i) c[i] = w;
- for (int i = 1; i <= n; ++i) {
- read (val);
- if (val> w) puts ("-1");
- else print (query (1, 1, h, val)), puts ("");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3331866.html