AT_abc174_e [ABC174E] 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$

输出格式

请输出答案的整数值。

样例 1

输入

2 3
7 9

输出

4

样例 2

输入

3 0
3 4 5

输出

5

样例 3

输入

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$
• 输入均为整数。

样例解释 1

• 首先，将长度为 $7$ 的原木在距离一端 $3.5$ 的位置切开，得到两根长度为 $3.5$ 的原木。
• 然后，将长度为 $9$ 的原木在距离一端 $3$ 的位置切开，得到长度为 $3$ 和 $6$ 的原木。
• 最后，将长度为 $6$ 的原木在距离一端 $3.3$ 的位置切开，得到长度为 $3.3$ 和 $2.7$ 的原木。 这样，所有原木中最长的那根长度为 $3.5$。这是最小可能值，因此输出其向上取整 $4$。

由 ChatGPT 4.1 翻译