← 返回题目列表

AtCoder · abc174_e

E. 日志

中文机器翻译题面 查看原题

分数: 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