Poj 3258: River Hopscotch

poj3258.md

Poj 3258: River Hopscotch

題目

分析

最小值最大化 => 二分搜

※ 這篇包含了一些個人猜想，有些東西不是那麼確定，未來可能修改

正負相關性判定

bool C(d) = 移除 M 個石頭後，可否使相鄰石頭間的最短距離大於等於 d

實作 C 時，改為計算相鄰石頭間距離小於 d 的有幾個，是否小於等於 M

另外，從定義可知：

if C(x) = true
then C(n) = true for all n <= x

也就是說，C(x) 表會是

1 1 1 1 1 0 0 0 0 0 0 0

這種形式，而我們的目標是尋找最後一個 1 發生在哪

上下界判定

這題使用 [lb, ub] 或 [lb, ub) 都可以，但各種的二分搜寫法不太一樣

下界應給它在還沒移除任何石頭前，相鄰石頭間最短距離， 但要計算出此值這種還需要多打一些程式碼，而且我們知道此值必大於 0， 所以根據定義，我們可以知道，C(0) = true，所以可以直接給下界值為 0

上界最大值發生在 N = M 的時候，即移除所有中間石頭，此時答案是 L

---

如果使用 [lb, ub)，則

int lb = 0, ub = L+1;

// 二分搜
while (ub - lb > 1) {
    int mid = (lb + ub) / 2;
    if (C(mid)) lb = mid;
    else ub = mid;
}

答案為 lb

---

使用 [lb, ub]

int lb = 0, ub = L; // 解的範圍：[lb, ub]

while (lb <= ub) {
    int mid = (lb + ub) / 2;
    if (C(mid)) lb = mid + 1;
    else ub = mid - 1;
}

上面程式跑完，lb 會落在 C(x) 表中的第一個 0 上面，相當於 lower_bound(lb, ub + 1, 0)， 所以答案是 lb - 1

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX_N = 50000;

int L, N, M;
int rocks[MAX_N + 2];

bool C(int d) {
    int cnt = 0;
    int prev = 0; // 前一個石頭是誰，初使值為起點 rocks[0]
    for (int i = 1; i < N + 1; i++) {
        if (rocks[i] - rocks[prev] < d) // 若相鄰距離 < d，移除 rocks[i]。
            cnt++;
        else
            prev = i; // 維護前一個石頭
    }

    // 終點與其前一個的情況
    if (rocks[N + 1] - rocks[prev] < d) {
        cnt++;
        // prev = N + 1 // 後面沒石頭了，沒必要繼續維護
    }

    return cnt <= M;
}

int solve() {
    sort(rocks + 1, rocks + N + 1);

    // ... 1 1 1 1 0 0 0 ...
    int lb = 0, ub = L + 1;
    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if (C(mid)) lb = mid;
        else ub = mid;
    }

    return lb;
}

int main() {
    scanf("%d %d %d", &L, &N, &M);
    for (int i = 1; i <= N; i++)
        scanf("%d", &rocks[i]);

    rocks[0] = 0;
    rocks[N+1] = L;

    printf("%d\n", solve());

    return 0;
}