POJ 3258 River Hopscotch：二分答案 + 貪心檢查最小跳躍最大化

問題建模

河長 L (≤10^9)，起點 0、終點 L，中間 N 塊石頭 (N≤50,000)。可移除最多 M 塊石頭。移除後，牛從 0 跳到 L，只能踩石頭。求最大化最小跳躍距離。

二分答案框架

• 檢查函數 check(x)：能否通過移除 ≤M 塊石頭，使所有相鄰石頭（含河岸）距離 ≥ x
• 貪心策略：從左向右掃描，若下一石頭距離 < x 則移除它，否則跳過去
• 二分範圍：[0, L]，找最大可行 x

核心代碼

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

const int MAXN = 50005;
long long stone[MAXN];
long long L; int N, M;

bool check(long long dist) {
    int removed = 0, last = 0; // last: 最後保留的石頭索引
    for (int i=1; i<=N+1; i++) {
        if (stone[i] - stone[last] < dist) removed++;
        else last = i;
    }
    return removed <= M;
}

int main() {
    while (scanf("%lld%d%d", &L, &N, &M) == 3) {
        for (int i=1; i<=N; i++) scanf("%lld", &stone[i]);
        stone[0] = 0; stone[N+1] = L;
        sort(stone+1, stone+N+1); // 石頭需排序！
        long long lo = 0, hi = L, ans = 0;
        while (lo <= hi) {
            long long mid = (lo + hi) >> 1;
            if (check(mid)) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

樣例演示

輸入:
25 5 2
2 14 11 21 17
排序後石頭: 0, 2, 11, 14, 17, 21, 25

移除 2 和 14:
跳躍: 0→11(11), 11→17(6), 17→21(4), 21→25(4)
最小跳躍 = 4（最優）

關鍵細節

• 石頭輸入無序，必須排序
• 檢查函數中 last 記錄上一個保留的石頭，而非上一個遍歷的
• 終點 L 視為第 N+1 塊石頭，不可移除
• 長整型防止溢出（L≤10^9）

複雜度

• 排序：O(N log N)
• 二分：O(log L) ≈ 30 次
• 每次檢查：O(N)
• 總計：O(N log N + N log L) ≈ 2×10^6 操作，極快