题目描述

有 N 根绳子，第 i 根绳子长度为 Li，现在需要 M 根等长的绳子，你可以对 N 根绳子进行任意裁剪（不能拼接），请你帮忙计算出这 M 根绳子最长的长度是多少。

输入格式

第一行包含 2 个正整数 N、M，表示原始绳子的数量和需求绳子的数量。

第二行包含 N 个整数，其中第 i 个整数 Li 表示第 i 根绳子的长度。

输出格式

输出一个数字，表示裁剪后最长的长度，保留两位小数。

样例

输入样例：
3 4
3 5 4
输出样例：
2.50

数据范围

1 ≤ N,M ≤ 100000
0 < Li < 10^9

算法1

(二分) $O(nlog(max(rope)))$

思路：从数据范围来看，在100000 以内，所以根据数据范围反推算法，可以得到或许可以用二分来做。
进一步分析可以发现答案的范围在0~max(rope)之间，其中的rope为绳子的长度数组。
那么可以得到一个结论就是，每次取mid时，若mid满足条件，则mid的左区间也一定满足条件；当mid不满足条件时，则mid的右区间也不会满足条件。因此可以使用浮点二分解决问题。

时间复杂度分析：二分的区间范围为[0,max(rope)]，所以该部分的时间复杂度为$O(log(max(rope)))$。每次二分时候，都需要遍历一遍rope数组，所以这部分时间复杂度为$O(n)$，所以最后的时间复杂度为$O(nlog(max(rope)))$。

ps.浮点二分，感觉时间二分次数并不是严格的以2为底的对数，不过不知道怎么分析了。。

Python 代码

n, m = list(map(int, input().split()))

rope = list(map(int, input().split()))

# 绳子长度范围
l, r = 0, max(rope)

# 注意浮点数二分的循环退出条件
while r - l > 1e-5:
    mid = (l + r) / 2

    # 在长度mid下能剪出多少根绳子
    cnt = 0
    for tmp in rope:
        cnt += tmp // mid

    # 不需要判断边界条件的问题
    if cnt >= m:
        l = mid
    else:
        r = mid

print('%.2f' % r)