A21074. 假设数组a的值域范围是D，以下程序的时间复杂度是O(nlog n+nlog D)。（ ）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…

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

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_sorted = a.copy()
    a_sorted.sort()

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

    while l < r:
        mid = (l + r + 1) // 2
        if check(n, a_sorted, 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)