E - Logs

得分：500分

问题描述

我们有 $N$ 根木材日志，其长度依次为 $A_1,A_2,\cdots A_N$。

我们最多能够在总共 $K$ 次切割木材。当一根长度为 $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$

输出

输出一个表示答案的整数。

2 3
7 9

4

• 首先，我们将长度为 $7$ 的木材在离其一端距离为 $3.5$ 处切割，得到两根长度都是 $3.5$ 的木材。
• 接下来，我们将长度为 $9$ 的木材在离其一端距离为 $3$ 处切割，得到两根长度分别为 $3$ 和 $6$ 的木材。
• 最后，我们将长度为 $6$ 的木材在离其一端距离为 $3.3$ 处切割，得到两根长度分别为 $3.3$ 和 $2.7$ 的木材。

在这种情况下，最长木材的长度是 $3.5$，这是最短的可能结果。将其向上取整为整数，输出结果为 $4$。

3 0
3 4 5

5

10 10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

292638192