分数: 500 点
问题陈述
我们有 N 长度对数 A_1,A_2,\cdots A_N.
我们最多可以切割这些原木 总共 K 次。当长度为 log L 在距离原木一端的距离为 t (0<t<L),它变成长度的两个对数 t 和 L-t.
找到最多之后的最长日志的最短可能长度 K 剪切,四舍五入为整数后打印。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \cdots A_N
输出
打印一个代表答案的整数。
示例输入 1
2 3 7 9
示例输出 1
4
- 首先,我们将切割长度的日志 7 到距离日志末端的距离为 3.5,产生两个长度的对数 3.5 每个。
- 接下来,我们将切割长度的日志 9 到距离日志末端的距离为 3,产生两个长度的对数 3 和 6.
- 最后,我们将切割长度的对数 6 到距离日志末端的距离为 3.3,产生两个长度的对数 3.3 和 2.7.
在这种情况下,日志的最长长度将为 3.5,这是可能的最短结果。舍入为整数后,输出应为 4.
示例输入 2
3 0 3 4 5
示例输出 2
5
示例输入 3
10 10 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202
示例输出 3
292638192