HDU 2795 Billboard：線段樹維護廣告牌剩餘寬度的經典應用

問題建模

有一塊高 h、寬 w 的廣告牌（h, w ≤ 10^9）。依次放入 n 張寬度為 w_i 的單位高度廣告（n ≤ 200,000）。放置規則：

1. 優先選擇最上方（行號最小）的可行位置
2. 同一行中優選最左側位置
3. 若無法放置，輸出 -1

本質上是對每一行維護「剩餘可用寬度」，每次查詢：找到第一個剩餘寬度 ≥ w_i 的行，並扣減該寬度。

線段樹優化關鍵觀察

• h 可能高達 10^9，但最多只能放 n 張廣告，因此有效行數不超過 n
• 構建線段樹時只需建立前 min(h, n) 行
• 每個節點維護區間內的 最大剩餘寬度
• 查詢時優先走左子樹（滿足「最上、最左」原則）

完整 AC 代碼

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
struct Node {
    int l, r;
    int maxWidth;  // 區間最大剩餘寬度
} seg[MAXN << 2];

int h, w, n;

void build(int l, int r, int rt) {
    seg[rt].l = l; seg[rt].r = r;
    if (l == r) {
        seg[rt].maxWidth = w;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    seg[rt].maxWidth = max(seg[rt << 1].maxWidth, seg[rt << 1 | 1].maxWidth);
}

// 查詢並更新：找到第一個能放下 width 的行
int query(int width, int rt) {
    if (seg[rt].l == seg[rt].r) {
        seg[rt].maxWidth -= width;
        return seg[rt].l;
    }
    if (seg[rt << 1].maxWidth >= width)
        return query(width, rt << 1);
    else
        return query(width, rt << 1 | 1);
}

int main() {
    while (scanf("%d%d%d", &h, &w, &n) == 3) {
        int rows = min(h, n);
        build(1, rows, 1);
        while (n--) {
            int width; scanf("%d", &width);
            if (width > seg[1].maxWidth) {
                puts("-1");
            } else {
                int row = query(width, 1);
                printf("%d\n", row);
            }
        }
    }
    return 0;
}

複雜度分析

• 構建樹：O(min(h, n))
• 每次查詢/更新：O(log min(h, n))
• 總時間：O(n log n)，空間 O(n)
• 完美應對 n=200,000 的數據規模

常見坑點提醒

1. h 超大時截取：rows = min(h, n)，否則構建樹會 MLE/TLE
2. 查詢順序固定左優先：保證「最上、最左」
3. 輸入多組測試數據：while(scanf(...)==3) 循環處理