前置知識

這題是「對答案二分搜」的經典入門題，下面的講解直接把它當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 對答案二分搜：NTUCPC Guide〈對答案二分搜〉——要帶走的是「答案序列長得像『否否否……是是是』就能二分」，它的例題之一正是本題；吳邦一《AP325》第 4 章 4.2.4「外掛二分搜」的 P-4-9 也是本題（教材 PDF 第 126～128 頁；Python 版第 4 章（II））。
• 排序：語法書 11.4（座標沒排序，先排）。

簡潔題意

數線上 \(N\) 個服務點（座標是整數、沒排序、可能重複），要架 \(K\) 座直徑都是 \(D\) 的基地台，一座蓋住長度 \(D\) 的一段（基地台不必架在服務點上）。求能讓每個服務點都被蓋到的最小整數直徑 \(D\)（\(K < N \le 50000\)，座標 \(\le 10^9\)；題目保證答案 \(\ge 1\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(10\) 分）：座標 \(\le 100\)，\(1 \le K \le 2\)，\(K < N \le 10\)。
• 子題組 2（\(20\) 分）：座標 \(\le 1000\)，\(1 \le K < N \le 100\)。
• 子題組 3（\(20\) 分）：座標 \(\le 10^9\)，\(1 \le K < N \le 500\)。
• 子題組 4（\(50\) 分）：座標 \(\le 10^9\)，\(1 \le K < N \le 50000\)。

先解一個簡單的問題：直徑 D 固定，要幾座？

直接問「最小直徑」不好下手，先把 \(D\) 固定住，問「\(K\) 座夠不夠蓋」。座標排序後從左往右看：最左邊還沒被蓋到的點一定要有一座基地台蓋它，而這一座放得越右越好——讓它的範圍從這個點開始、往右延伸 \(D\)，就是 \([x, x + D]\)。接著跳過所有座標 \(\le x + D\) 的點，再從下一個沒被蓋到的點放下一座。數一數放了幾座，不超過 \(K\) 就是「可以」。

為什麼「從最左邊的點開始放」不會吃虧？蓋住最左邊的點的那一座，往右移到左端剛好對齊它，蓋到的點只會變多不會變少——所以一定有一個最省的放法長這樣。寫成函式：

// 直徑 d 的基地台，k 座夠不夠蓋住所有點（p 已排序）
bool enough(long long d) {
    int used = 0;
    long long coveredTo = -1;                 // 目前蓋到哪裡
    for (int i = 0; i < n; i++) {
        if (p[i] > coveredTo) {               // 這個點還沒被蓋到：放一座
            used++;
            coveredTo = p[i] + d;
        }
    }
    return used <= k;
}

先拿下 30 分：D 從 1 開始一個一個試

子題組 1、2 的座標不超過 \(1000\)，答案也不會超過 \(1000\)：\(D\) 從 \(1\) 開始往上試，第一個「可以」的就是答案。每試一次掃一遍 \(N\) 個點，最多 \(1000 \times 100\) 次，眨眼就完。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 50005;
long long p[MAX_N];
int n, k;

// 直徑 d 的基地台，k 座夠不夠蓋住所有點（p 已排序）
bool enough(long long d) {
    int used = 0;
    long long coveredTo = -1;                 // 目前蓋到哪裡
    for (int i = 0; i < n; i++) {
        if (p[i] > coveredTo) {               // 這個點還沒被蓋到：放一座
            used++;
            coveredTo = p[i] + d;
        }
    }
    return used <= k;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> p[i];
    sort(p, p + n);                           // 題目明說座標沒排序
    long long d = 1;                          // 答案至少是 1
    while (!enough(d)) d++;                   // 子題組 1、2：座標 ≤ 1000，最多試 1000 次
    cout << d << '\n';
    return 0;
}

這份程式交上去，座標到 \(10^9\) 的測資會 TLE（最壞要試 \(10^9\) 次）——這是正常的，逐筆給分之下子題組 1、2 的 \(30\) 分穩穩到手。

從 30 分到 100 分：對 D 二分搜

圖 1 下排那一列就是關鍵：\(D\) 從小到大，結果一定是「不行、不行、……、可以、可以、……」——因為某個 \(D\) 可以，更長的直徑用同樣的放法一定也可以。所以不必一個一個試，用二分搜找第一個「可以」的 \(D\)：範圍 \([1, \text{最大座標} - \text{最小座標}]\)（右端一定可以：一座就全蓋），每次取中間試，可以就往左縮、不行就往右縮。

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> p[i];
    sort(p, p + n);                           // 題目明說座標沒排序
    long long lo = 1, hi = max(1LL, p[n - 1] - p[0]);   // hi：一座就能全蓋，一定可以
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (enough(mid)) hi = mid;            // 可以：答案在 mid 或更左
        else lo = mid + 1;                    // 不行：答案在 mid 右邊
    }
    cout << lo << '\n';
    return 0;
}

enough 原封不動。二分搜最多試約 \(30\) 次（\(2^{30} > 10^9\)），每次掃 \(N = 50000\) 個點，加上排序，總共遠低於 \(1\) 秒。hi 用 max(1LL, …) 是因為所有點座標相同時最大減最小是 \(0\)，而題目保證答案至少是 \(1\)。

測過再交：範例的點都不重複、K 都很小

兩個範例都是五個相異座標、\(K = 1\) 和 \(2\)。沒蓋到的：座標重複、所有點都一樣（答案要是 \(1\) 不是 \(0\)）、\(K = N - 1\)（每座只要蓋相鄰兩點中最近的那對）、剛好差 \(D\) 的兩點能不能共用一座。

五筆都親眼看過正確，這題就穩了。