HDU 1257 最少攔截系統：貪心 + 二分優化的 LIS 變體

問題轉化

導彈高度序列，每套系統只能攔截「遞減」高度的導彈。求覆蓋整個序列所需的最少系統數。
等價於：將序列分解為最少數量的非遞增子序列。
由 Dilworth 定理：最少非遞增子序列數 = 最長嚴格遞增子序列（LIS）長度。

貪心模擬：維護各系統「當前可攔截的最大高度」

遍歷導彈高度 h：
1. 找到第一個 cur_max[i] > h 的系統，更新 cur_max[i] = h
2. 若不存在，開新系統 cur_max[ans++] = h
為求最少系統數，應選 cur_max[i] 中 最小的大於 h 的值（類似 patience sorting）。

O(N log N) 優化：二分查找

cur_max 數組始終保持遞增（證明：若 i < j 則 cur_max[i] < cur_max[j]），可用 lower_bound 找第一個 > h 的位置。

完整代碼

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

const int MAXN = 30000 + 10;
int a[MAXN], cur_max[MAXN];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 找第一個 > a[i] 的位置
            int pos = lower_bound(cur_max, cur_max + ans, a[i] + 1) - cur_max;
            // 注意：要嚴格大於，所以找 a[i]+1 的 lower_bound
            // 或用 upper_bound(cur_max, cur_max+ans, a[i])
            cur_max[pos] = a[i];
            if (pos == ans) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

原始代碼的 O(N²) 寫法與優化對比

// 原始雙層循環 O(N²)
for (int i = 1; i < n; i++) {
    int dis_min = INF;
    for (int j = 0; j < ans; j++) {
        if (a[i] < cur_max[j] && dis_min > cur_max[j]) 
            dis_min = j;
    }
    if (dis_min == INF) dis_min = ans++;
    cur_max[dis_min] = a[i];
}

• 原版：內層遍歷所有系統，找「大於 h 且最小」的 —— O(N²)
• 優化版：利用 cur_max 遞增特性，upper_bound 直接定位 —— O(N log N)

核心證明：為什麼 cur_max 單調遞增？

假設系統 i 建立早於系統 j，則系統 i 的最後導彈高度 ≤ 系統 j 的最後導彈高度。否則系統 i 完全可以攔截系統 j 的最後一發導彈，矛盾。因此 cur_max[i] < cur_max[j] 恆成立。