AI题库 · GESP-Python五级题库
题目分享 #24880
假设数组a的值域范围是D,以下程序的时间复杂度是O(nlogn+nlogD)。
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)
1
对
0
错
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。