木材加工

题目背景

要保护环境

题目描述

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

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

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

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

输入格式

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

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

输出格式

仅一行，即的最大值。

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

样例 #1

样例输入 #1

样例输出 #1

114

提示

数据规模与约定

对于的数据，有，，。

题解

以样例分析，n = 3,即三根木头；k = 7,即截成 7小段木头，求小段木头可截的最大长度x,给出三段木头的长度：232,124,456 。

为了和左边界 l 区分，我们把题目中木段长度 l 统一换为 x

用暴力思想：x = 1cm，一：232//1 = 232；二：124//1 = 124；三：456//1 = 456
则k = 232 + 124 + 456 = 812
即 x = 1,k = 812, 同理得：
x = 2, k = 406, x = 3, k = 270, …… x = 80, k = 8,x = 81, k = 8, …… x = 95, k = 7,
x = 96, k = 7, …… x = 115,k =6, x = 116,k = 6,
……
由此发现答案具有单调性，且 k = 7时 x 是一段区间,我们找到第一个k = 6的x然后x - 1即是k = 7时每段最大的长度

用二分答案：由题意知， k 不为零时x最大为456，则正确答案一定就在 1—456 这个区间里。
即 l = 1,r = 456 ，mid = (l+r)//2

我们定义一个让你的代码简洁明了的check函数，x = mid,根据x和k的单调性，就是咱们用sum += a[i]//x,sum就是咱们求出的段数，和题目已知段数k做对比，如果 sum = k，返回 Ture，说明咱们目前的x小于正确答案，正确答案大于 x，然后用ans记录当前mid,以防这个mid是正确答案（记录最佳答案）跳出循环后 ans就是最佳答案。然后应该把左边界l = mid+1,以缩短 x的范围。

如果sum < k,则说明mid大于正确答案,正确答案小于mid，所以应该把右边界r = mid - 1。

n, k = map(int, input().split())
a = []
for i in range(0, n):
    x = int(input())
    a.append(x)
a.sort()


def check(x):
    sum = 0
    for i in range(0, n):
        sum += a[i] // x
    if sum >= k:
        return True
    else:
        return False


l = 1
r = a[n - 1]
ans = 0
while l <= r:
    # 欧耶耶，l = r，mid = l = r,存在 mid，如果没有=，则mid不存在？
    mid = (l + r) // 2
    if check(mid):
        l = mid + 1
        ans = mid
    else:
        r = mid - 1
print(ans)

Shineria's Blog

洛谷P2440 木材加工题解