P2440 木材加工（py）

题目背景

要保护环境

题目描述

木材厂有 nn 根原木，现在想把这些木头切割成 kk 段长度均为 ll 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 ll 的最大值。

木头长度的单位是 cmcm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 1111 和 2121，要求切割成等长的 66 段，很明显能切割出来的小段木头长度最长为 55。

输入格式

第一行是两个正整数 n,kn,k，分别表示原木的数量，需要得到的小段的数量。

接下来 nn 行，每行一个正整数 LiLi​，表示一根原木的长度。

输出格式

仅一行，即 ll 的最大值。

如果连 1cm1cm 长的小段都切不出来，输出 0。

输入输出样例

输入 #1复制

3 7
232
124
456

输出 #1复制

114

说明/提示

数据规模与约定

对于 100%100% 的数据，有 1≤n≤1051≤n≤105，1≤k≤1081≤k≤108，1≤Li≤108(i∈[1,n])1≤Li​≤108(i∈[1,n])。

可以用二分 答案

使用技巧：

1）问题可以被归纳为找到使得某命题p(x)成立（或不成立）的最大（或最小x）。

2）把p(x)看作一个值为真或假的函数，那么它一定在某个分界线的一侧全为真，另一侧全为假。

def val(num, ans):
    k = 0
    for i in num:
        k += i // ans
    return k


def find(num, l, r, k):
    max_len = 0
    while l <= r:
        mid = (l + r) // 2
        if val(num, mid) < k:
            r = mid - 1
        elif val(num, mid) >= k:
            max_len = mid# 记录可能的答案
            l = mid + 1 #找到最大的x，让命题成立
    return max_len


if __name__ == "__main__":
    n, k = map(int, input().split())
    max_x = 0
    ans = 0
    wood = []
    for _ in range(n):
        wood.append(int(input()))
        ans += wood[-1]
    max_meter = ans // k # 缩小范围
    print(find(wood, 1, max_meter, k))