導彈高度序列 H[1..N]，攔截系統特性：首發任意高度，後續不得超過前一發。求攔截所有導彈所需最少系統數。
等價於：將序列分解為最少數量的非遞增子序列。由 Dilworth 定理，答案 = 最長嚴格遞增子序列 (LIS) 長度。
top[k]：第 k 個系統當前攔截高度（即該非遞增子序列最後一個元素）h：
top 中找到第一個 > h 的位置（上界），替換為 htop[++cnt] = h）top 始終嚴格遞增，可用二分查找#include#include #define MAXN 100000 int top[MAXN]; int main() { int n, h; while (scanf("%d", &n) == 1) { int cnt = 0; for (int i = 0; i < n; i++) { scanf("%d", &h); int l = 0, r = cnt; // 在 top[0..cnt-1] 中找上界 while (l < r) { int mid = (l + r) >> 1; if (top[mid] > h) r = mid; else l = mid + 1; } if (l == cnt) top[cnt++] = h; // 新系統 else top[l] = h; // 替換現有系統頂 } printf("%d\n", cnt); } return 0; }
Input: 8 389 207 155 300 299 170 158 65 Process: h=389: top=[389] cnt=1 h=207: top=[207] (替換 389) h=155: top=[155] h=300: top=[155,300] (新系統) h=299: top=[155,299] h=170: top=[155,170] h=158: top=[155,158] h=65: top=[65,158] Output: 2
| 概念 | 本題含義 |
|---|---|
| top[i] | 第 i 個攔截系統最後攔截高度 |
| 上界查找 | 找第一個 > h 的系統，讓高度損失最小 |
| 貪心證明 | 保持 top 單調，確保後續導彈選擇餘地最大 |
| 複雜度 | O(N log N)，N ≤ 100000 輕鬆通過 |
需額外記錄每個導彈所屬系統編號，用前驅指針回溯，屬於「耐心排序」完整實現。
導彈攔截問題是貪心 + 二分查找的經典應用。核心洞見：維護各系統頂部高度單調遞增，新導彈總選擇「能攔截且損失最小」的系統。此模式廣泛適用於「最少非遞增子序列分解」、「最長遞增子序列長度」等問題。
