单选题 适中
#24865

下面程序的运行结果为()。 def check(n, a, k, dist): cnt = 1 last = a[0] for i in range(1, n)…

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

def check(n, a, k, dist):
    cnt = 1
    last = a[0]

    for i in range(1, n):
        if a[i] - last >= dist:
            cnt += 1
            last = a[i]

    return cnt >= k

def solve(n, a, k):
    a.sort()

    l = 0
    r = a[-1] - a[0]

    while l < r:
        mid = (l + r + 1) // 2
        if check(n, a, k, mid):
            l = mid
        else:
            r = mid - 1

    return l

if __name__ == "__main__":
    a = [1, 2, 8, 4, 9]
    n = 5
    k = 3
    result = solve(n, a, k)
    print(result)


未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析
函数 check 接收四个参数:n 表示数组长度,a 为升序排列的数值数组,k 为目标数量,dist 为最小距离。遍历数组 a,统计满足相邻元素差值不小于 dist 的元素个数 cnt,返回 cnt 是否大于等于 k。函数 solve 对数组 a 排序后,使用二分查找确定最大化的最小距离。左边界 l 初始化为 0,右边界 r 初始化为数组最大值与最小值之差。在二分过程中,计算中点 mid,通过 check 函数判断是否存在至少 k 个元素,其相邻元素间距离不小于 mid。若满足条件,则尝试增大距离;否则减小距离。循环持续至区间收敛。