单选题
适中
#24868
给定n 根木头,第i 根长度为a [i]。要切成不少于m 段等长木段,求最大可能长度,则横线上应填写()。 def check(a, m, x): cnt =…
给定n 根木头,第i 根长度为a [i]。要切成不少于m 段等长木段,求最大可能长度,则横线上应填写()。
def check(a, m, x): cnt = 0 for length in a: if x == 0: return True cnt += length if cnt >= m: return True return cnt >= m def main(): import sys input = sys.stdin.read().split() idx = 0 n = int(input[idx]) idx += 1 m = int(input[idx]) idx += 1 a = [] mx = 0 for _ in range(n): num = int(input[idx]) idx += 1 a.append(num) mx = max(mx, num) l = 1 r = mx ans = 0 while l <= r: mid = l + (r - l) // 2 if check(a, m, mid): ans = mid _________________ else: _________________ print(ans) if __name__ == "__main__": main()
答案与解析
正确答案:A
解析
使用二分查找确定最大可能长度。左边界为1,右边界为最长木头的长度。每次取中点作为候选长度,通过check函数验证是否能切出至少m段。若可以,则尝试更大的长度,更新左边界;否则尝试更小的长度,更新右边界。循环直至区间收敛,得到最大可行解。