UVA 1372 Log Jumping：木板跳躍環判定的貪心策略

問題描述

給定 n 塊木板，每塊有起始位置和固定長度 k。木板之間若重疊則可互相跳躍。求能構成「跳躍環」的最大木板數量（即最大連通分量大小）。

核心觀察

• 木板按起始位置排序後，重疊關係具有傳遞性：若 A 與 B 重疊、B 與 C 重疇，則 A、B、C 兩兩可達
• 「環」實為連通分量：任意兩塊木板間存在跳躍路徑
• 只需檢查相鄰木板是否重疊即可判定連通性

貪心掃描演算法

1. 將所有木板起始位置排序
2. 掃描維護當前連通分量：

sort(start, start + n);
int ans = 0, i = 0;
while (i < n) {
    int sum = 1;  // 當前分量大小
    // 擴展分量：檢查下一塊木板是否與當前分量「邊界」重疊
    while (i < n-1 && 
           (sum == 1 && check(start[i], start[i+1]) ||  // 首塊只需與下一塊重疊
            check(start[i], start[i+1]) && check(start[i-1], start[i+1]))) { // 後續需與前兩塊均重疊
        sum++; i++;
    }
    if (!check(start[i], start[i+1]) || i == n-1) i++; // 跳過不重疊或結束
    ans = max(ans, sum);
}
printf("%d\n", ans);

關鍵函數

bool check(int s, int e) { return e - s <= k; } // 起點差 ≤ 長度 即重疊

為何檢查前兩塊？

考慮木板長度固定為 k，位置遞增。若木板 i+1 與 i 重疊，且 i 與 i-1 重疇，則 i+1 必與 i-1 重疊（區間交的傳遞性）。但為了嚴謹，代碼顯式檢查 check(start[i-1], start[i+1])。

複雜度分析

• 排序：O(n log n)
• 掃描：O(n)
• 總體：O(n log n)，n ≤ 5000 極其高效

完整代碼

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

const int N = 5005;
int start[N];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, k; scanf("%d%d", &n, &k);
        for (int i = 0; i < n; ++i) scanf("%d", &start[i]);
        sort(start, start + n);
        
        int ans = 0, i = 0;
        auto check = [k](int s, int e) { return e - s <= k; };
        
        while (i < n) {
            int sum = 1;
            while (i < n-1 && 
                   (sum == 1 && check(start[i], start[i+1]) ||
                    check(start[i], start[i+1]) && check(start[i-1], start[i+1]))) {
                sum++; i++;
            }
            if (!check(start[i], start[i+1]) || i == n-1) i++;
            ans = max(ans, sum);
        }
        printf("%d\n", ans);
    }
    return 0;
}

延伸思考

若木板長度不固定，需維護當前分量的「最右覆蓋端點」，判斷新木板起點 ≤ 當前最右端點即可合併，這是經典的區間合併/連通分量問題模板。