单选题 适中
#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段。若可以,则尝试更大的长度,更新左边界;否则尝试更小的长度,更新右边界。循环直至区间收敛,得到最大可行解。