HDU 2795 Billboard：線段樹區間最大值查詢——廣告牌貼紙最優佈局

HDU 2795 Billboard：線段樹區間最大值查詢——廣告牌貼紙最優佈局

題目來源：HDOJ 2009 Summer Exercise（5）
核心標籤：線段樹、區間最大值、貪心策略

題目大意

一塊 h × w 的廣告牌（h, w ≤ 10^9），依序貼上 n 張高度為 1、寬度為 w_i 的公告。貼紙規則：

1. 優先選擇最上方可行的行
2. 同一行中優選最左側位置
3. 無法放置則輸出 -1

對每張公告輸出其所在行號（1-based）。n ≤ 200,000，多測資（≤ 40 組）。

關鍵觀察：行數上界與線段樹建模

因每張公告高度為 1，最多只會用到前 min(h, n) 行。若 h > n，多餘行永遠用不到，直接令 h = n。將每一行的剩餘寬度視為數值，建立線段樹維護區間最大剩餘寬度。根節點的 Max 即為當前廣告牌最寬的可用空間。

線段樹節點結構

struct Node {
    int l, r;   // 區間 [l, r] 代表行號範圍
    int Max;    // 該區間內「剩餘寬度最大的那一行」的剩餘寬度
} s[200000 * 4];

建樹：初始化所有行剩餘寬度為 w

void InitTree(int l, int r, int k, int w) {
    s[k].l = l; s[k].r = r; s[k].Max = w;
    if (l == r) return;
    int mid = (l + r) >> 1;
    InitTree(l, mid, k<<1, w);
    InitTree(mid+1, r, k<<1|1, w);
}

更新與查詢合一：遞歸尋找最上、最左可放置行

void UpdateTree(int ww, int k) {
    if (s[k].l == s[k].r) {           // 到達葉子節點 = 找到目標行
        printf("%d\n", s[k].l);       // 輸出行號
        s[k].Max -= ww;               // 扣除已用寬度
        return;
    }
    // 優先走左子樹（行號較小 = 更上方）
    if (ww <= s[k<<1].Max)
        UpdateTree(ww, k<<1);
    else
        UpdateTree(ww, k<<1|1);
    // 回溯更新區間最大值
    s[k].Max = max(s[k<<1].Max, s[k<<1|1].Max);
}

主流程

while (~scanf("%d%d%d", &h, &w, &n)) {
    if (h > n) h = n;                 // 行數上界優化
    InitTree(1, h, 1, w);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &ww);
        if (s[1].Max >= ww)           // 根節點最大值 ≥ 當前公告寬度
            UpdateTree(ww, 1);
        else
            printf("-1\n");           // 無法放置
    }
}

複雜度分析

• 建樹：O(h)，h ≤ n ≤ 2e5
• 單次操作：O(log h)
• 總時間：O(n log n)，空間 O(n)

核心技巧總結

1. 行數壓縮：h = min(h, n) 將 1e9 規模壓縮至 2e5
2. 線段樹存「區間最大值」：而非單點值，直接支援「最上最左」貪心查詢
3. 查詢即更新：遞歸下行時順便完成放置與扣減，無需額外查詢步驟

此題展示了線段樹解決「二維佈局一維化 + 貪心查詢」的經典模式，同類問題包括電影院選座、停車場管理等。