Logs

题目描述

我们有 $N$ 根长度为 $A_1,A_2,\cdots A_N$ 的木材。 我们最多可以总共切割 $K$ 次这些木材。当一根长度为 $L$ 的木材在距某端为 $t$ 的位置被切割时（$0<t<L$），它变成两根长度为 $t$ 和 $L-t$ 的木材。 在最多 $K$ 次切割后，求可能达到的最长木材的最短可能长度，并将其向上取整为整数后输出。

输入格式

输入按如下格式从标准输入给出： $N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

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

2 3
7 9

4

3 0
3 4 5

5

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

292638192

提示

$1 \leq N \leq 2 \times 10^5$ $0 \leq K \leq 10^9$ $1 \leq A_i \leq 10^9$ 输入中的所有数值均为整数。首先，我们将长度为 $7$ 的木材在距某端 $3.5$ 的位置切割，得到两根长度均为 $3.5$ 的木材。 接着，我们将长度为 $9$ 的木材在距某端 $3$ 的位置切割，得到两根长度为 $3$ 和 $6$。 最后，我们将长度为 $6$ 的木材在距某端 $3.3$ 的位置切割，得到两根长度为 $3.3$ 和 $2.7$。

在此例中，木材的最长长度为 $3.5$，这是能够达到的最短可能结果。向上取整为整数后，输出应为 $4$.

标签: AtCoder|abc174E

来源

AtCoder|abc174E