GESP 七级 · GESP 202603 C++ 七级 第 7 题

下面程序的运行结果为（ ）。

#include <iostream>
#include <algorithm>

bool check(int n, int a[], int k, int dist) {
    int cnt = 1;
    int last = a[0];

    for (int i = 1; i < n; i++) {
        if (a[i] - last >= dist) {
            cnt++;
            last = a[i];
        }
    }

    return cnt >= k;
}

int solve(int n, int a[], int k) {
    std::sort(a, a + n);

    int l = 0;
    int r = a[n - 1] - a[0];

    while (l < r) {
        int mid = (l + r + 1) / 2;

        if (check(n, a, k, mid))
            l = mid;
        else
            r = mid - 1;
    }

    return l;
}

int main() {
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;
    int k = 3;

    std::cout << solve(n, a, k) << std::endl;

    return 0;
}

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

模拟执行时注意：① 循环变量的起始和终止值；② 递归的边界条件；③ 数据类型转换和精度问题。

【考点】排序｜二分查找｜最大化最小值

🎯 考纲定位：本題出自 GESP 七級算法模塊，核心考察「二分答案」與「最大化最小值」經典模型。命題人刻意選取距離判斷函數，卡住大量考生對二分邊界與單調性的理解——許多人會把二分對象誤認為數組下標或答案直接猜測，導致在檢查函數中計數錯誤。

🧠 解题思维：1. 排序：距離判斷依賴數組有序，否則 a[i]-last 無意義。2. 範圍：答案必在 [0, a[n-1]-a[0]] 間。3. 單調性：若距離 d 可行，任意更小的 d 必可行，滿足二分前提。4. 檢查：cnt 從 1 開始，遍歷時若 a[i]-last≥mid 則 cnt++，最後判斷 cnt≥k。5. 二分：mid=(l+r+1)/2 避免死循環，若可行則 l=mid，否則 r=mid-1。

🪤 陷阱拆解：A 選項 2 是典型二分死循環錯誤——用 mid=(l+r)/2 且條件不單調時會陷入無限。C 選項 4 是未排序後的誤判，直接取數組最大差值 9-1=8 誤以為答案。D 選項 5 更荒謬，連排序都跳過。檢查函數中 cnt=1 的初始化是關鍵，若忘記會導致 cnt 永遠為 0。二分上界若設為 a[n-1] 而非 a[n-1]-a[0]，會把答案縮小。

🔄 反命题思维：若將題目改為「最小化最大距離」（經典最小化最大值模型），答案會變成 2 或 1，因為檢查函數需確保所有選中元素間距≤d。若 k 增加至 4，答案必為 2。若去掉排序，直接取原始數組最大差值 8，則答案變成 D。刷到類似題時，先問自己「二分的對象是什麼？單調性在哪？」