[ABC174E] Logs
题意翻译
有 $n$ 个数 $a_1,a_2\dots a_n$。你要进行最多 $k$ 次操作。
每一次操作可以选一个数 $a_i$，将它分成 $t,a_i-t(0<t<a_i)$ 两个数。求问操作完后最大的数最小是多少，请向上取整输出。
translate by @Fire_flame
题目描述
[problemUrl]: https://atcoder.jp/contests/abc174/tasks/abc174_e
丸太が $ 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输出样例 #1
4输入样例 #2
3 0
3 4 5输出样例 #2
5输入样例 #3
10 10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202输出样例 #3
292638192说明
### 制約
- $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
- $ 0\ \leq\ K\ \leq\ 10^9 $
- $ 1\ \leq\ A_i\ \leq\ 10^9 $
- 入力はすべて整数である。
### Sample Explanation 1
\- まず、長さ $ 7 $ の丸太を片端から $ 3.5 $ の位置で切り、長さ $ 3.5 $ の丸太二本に分けます。 - 次に、長さ $ 9 $ の丸太を片端から $ 3 $ の位置で切り、長さ $ 3 $ と $ 6 $ の丸太に分けます。 - 最後に、長さ $ 6 $ の丸太を片端から $ 3.3 $ の位置で切り、長さ $ 3.3 $ と $ 2.7 $ の丸太に分けます。 すると、最も長い丸太の長さは $ 3.5 $ になります。これが最小なので、小数点以下を切り上げた $ 4 $ を出力します。