FZU 2041 Checker：貪心 + 模擬求最大空隙擴展

問題描述

給定長度 n 的 0/1 序列（1 為障礙，0 為空隙），以及操作次數 m。每次操作可將一個 1 移動到相鄰的 0 位置（即交換相鄰 0/1）。求經過 ≤ m 次操作後，連續 0 的最大長度。若無法操作輸出原最大長度。

核心思路：枚舉空隙 + 貪心雙向擴展

1. 預處理：記錄所有連續 0 段（空隙）的左右端點 [L, R] 和長度 len。在序列首尾虛擬添加 1 邊界。
2. 對每個空隙 i，嘗試向左、向右「吃」掉相鄰的 1（即將 1 移走），每吃一個 1 需要花費步數 = 該 1 到空隙邊界的距離。
3. 貪心策略：優先吃距離較近的側（左右獨立計算最近 1 的距離，取小者先吃），直到操作數 m 耗盡或無 1 可吃。
4. 記錄過程中空隙長度的最大值。

代碼實現要點

struct Gap { int l, r, len; };  // [l, r] 為 1 的位置，中間為 0 段
vector gaps;
int a[MAXN];  // 1 為障礙，0 為空

// 對每個 gap 計算可擴展長度
for (each gap) {
    int steps = m;
    int cur_len = gap.len;
    // 向左找最近的 1
    // 向右找最近的 1
    // 貪心取近者擴展，更新 steps, cur_len, 更新左右邊界
    // 記錄最大 cur_len
}

複雜度

空隙數 ≤ n，每個空隙擴展過程中每次操作消耗一個 1，總操作數 ≤ n。整體 O(n) 或 O(n log n)（若用集合維護 1 位置）。n ≤ 600 極小，直接模擬即可。

關鍵點

1. 虛擬邊界簡化邊界判斷。
2. 貪心證明：吃近的 1 總是不劣於吃遠的，因為步數成本更低，留給後續更多機會。
3. 操作數 m 可能很大，但實際可吃的 1 有限，循環自然終止。