单选题 适中
#24811

下面程序的运行结果为( )。 #include <iostream> #include <algorithm> bool check(int n, int a[…

下面程序的运行结果为( )。

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


未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析
程序包含两个函数:check 和 solve。check 函数接收数组 a、其长度 n、整数 k 和 dist,判断在排序后的数组中能否选出至少 k 个元素,使得相邻被选元素之间的差值不小于 dist。通过贪心策略遍历数组,统计满足条件的元素个数 cnt,并与 k 比较返回布尔结果。solve 函数先对数组排序,然后使用二分查找确定最大化的最小距离。左边界 l 初始化为 0,右边界 r 初始化为最大值与最小值之差。在 while 循环中,取 mid 为当前尝试的距离,根据 check 结果调整边界:若满足则增大下界,否则减小上界。最终逼近最优解。主函数调用 solve 并输出结果。