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

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

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 五级"数组与排序"模块。命题人把排序和二分搜索绑在一起考，因为单纯排序题太基础，而二分搜索需要构造单调谓词，五级正好卡住只会背模板、不懂"为什么单调"的考生。

解题思维：先排序让元素有序，才能用贪心检查"最小间距 dist 下能选多少个"。check 函数是单调的：dist 越大能选的数量越少。solve 用二分搜索答案区间[0, 最大值差]，mid = (l+r+1)/2 保证收敛，check 为真时 l=mid，否则 r=mid-1。最终 l 就是最大可行的 dist。

陷阱拆解：A 是只试了 dist=4 就以为答案，没意识到 dist=3 才刚好满足 k=3；D 是误以为间距可以取到最大值差 8，但贪心选不出 3 个；C 把二分搜索当成线性搜索，mid 取值错误导致死循环。最阴险的是 check 里的">= dist"——间距必须达到 dist 才算，小于 dist 的元素会被忽略，很多人会误写成"> dist"。

反命题思维：把 k 改成 4，答案变为 2；把数组改成无序，先排序再算，答案不变；改成"最多能选多少个元素使得间距≥dist"，那就要用二分搜索求最大的 count。刷到类似题先问自己"这题要二分什么？check 的单调性在哪？"