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

假设数组 $a$ 的值域范围是 $D$，以下程序的时间复杂度是 $O(n \log n + n \log D)$。

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;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】排序｜二分答案｜贪心策略

命中考纲五级“二分答案”核心考点。命题人刻意用 $O(n \log D)$ 代替 $O(D)$ 线性扫描，卡住只会暴力枚举的考生。

先排序 $O(n \log n)$ 是基础；答案范围 $[0, D]$ 具有单调性，用二分将搜索空间压缩 $O(\log D)$ 倍，check 函数线性扫描 $O(n)$。

错项 B 的陷阱在于忽视单调性：若直接用 $O(D)$ 遍历距离，当 $D \approx 10^9$ 时必 TLE；check 函数里的贪心策略（选最左可行点）才是关键。

若把 $k$ 改为“找最小间距”，check 函数需反转条件；若去掉排序，贪心失效。牢记：二分答案的前提是“若 mid 可行，则所有小于 mid 的值必可行”。