題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P3467 [POI 2008] PLA-Postering

Problem Statement

題目簡述

給定一排緊貼在一起的建築，第 ii 棟建築的寬為 did_i、高為 wiw_i。
要用若干張互不重疊的矩形海報，完整覆蓋這一整排建築的北側立面。
海報邊必須與座標軸平行，可以共邊但不能重疊，求最少需要幾張海報。

Constraints

約束條件

  • 1≤n≤2500001 \le n \le 250000
  • 1≤di,wi≤1091 \le d_i, w_i \le 10^9

思路：單調棧維護「目前還能往右延伸」的高度

先把每一棟建築都獨立貼一張海報，答案一開始最多是 nn。

接著思考：什麼情況下，當前這棟建築可以不用新增海報？

若目前高度是 hh，而左邊存在某棟高度也為 hh 的建築，且它們之間所有建築高度都至少是 hh，那麼這些建築在高度 hh 這一層可以連成同一個矩形海報，因此這一棟不必再開新海報，且中間的建築海報數量也不會增加。

換句話說，對每個 hih_i，我們只在乎：

  • 左側最後一個沒有被更低建築截斷、因此仍可能延伸到這裡的高度。
  • 如果那個高度剛好等於 hih_i，這一棟就能和前面共用同一張海報。

使用 單調棧(Monotonic Stack) 維護即可。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)
    每個高度最多進棧一次、出棧一次。
  • 空間複雜度：O(n)\mathcal{O}(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solve():
    n = int(input())
    items = [tuple(map(int, input().split())) for _ in range(n)]

    ans = n
    st = []  # 維護高度非遞減的堆疊
    for _, h in items:
        while st and st[-1] > h:
            st.pop()
        if st and st[-1] == h:
            ans -= 1
        st.append(h)
    print(ans)


if __name__ == "__main__":
    solve()