您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 3258 River Hopscotch：二分答案求最大化最短跳躍距離

編輯：關於C++

POJ 3258 River Hopscotch 完整解析

河流長度 L，起點終點固定，中間有 N 塊石頭（N ≤ 50,000）。可移除最多 M 塊石頭，求移除後「最短跳躍距離」的最大可能值。L 可達 10⁹，需 O(N log L) 演算法。

核心思路：二分答案 + 貪心驗證

二分搜尋「最短跳躍距離」的候選值 mid，驗證能否透過移除 ≤ M 塊石頭使所有相鄰石頭距離 ≥ mid。

驗證函數邏輯

從起點開始，維護上一個保留的石頭位置 last。遍歷所有石頭（含終點）：

若 current - last < mid：此石頭必須移除，計數器++
否則：保留此石頭，更新 last = current

最終若移除數 ≤ M，說明 mid 可行，嘗試更大值；否則 mid 過大，需縮小。

完整 AC 程式碼

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

const int MAXN = 50005;
int rock[MAXN]; // 石頭位置，含起點 0 和終點 L

bool check(int min_dist, int n, int m) {
    int removed = 0;
    int last = 0; // 起點位置
    for (int i = 1; i <= n; i++) {
        if (rock[i] - last < min_dist) {
            removed++; // 移除此石頭
        } else {
            last = rock[i]; // 保留
        }
    }
    return removed <= m;
}

int main() {
    int L, N, M;
    while (scanf("%d %d %d", &L, &N, &M) == 3) {
        for (int i = 1; i <= N; i++) scanf("%d", &rock[i]);
        
        rock[0] = 0;
        rock[N + 1] = L;
        sort(rock, rock + N + 2); // 確保有序
        
        int left = 1, right = L, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(mid, N + 1, M)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}