/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えとなる整数を出力せよ。
入力例 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
Score : 500 points
Problem Statement
We have N logs of lengths A_1,A_2,\cdots A_N.
We can cut these logs at most K times in total. When a log of length L is cut at a point whose distance from an end of the log is t (0<t<L), it becomes two logs of lengths t and L-t.
Find the shortest possible length of the longest log after at most K cuts, and print it after rounding up to an integer.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_N
Output
Print an integer representing the answer.
Sample Input 1
2 3 7 9
Sample Output 1
4
- First, we will cut the log of length 7 at a point whose distance from an end of the log is 3.5, resulting in two logs of length 3.5 each.
- Next, we will cut the log of length 9 at a point whose distance from an end of the log is 3, resulting in two logs of length 3 and 6.
- Lastly, we will cut the log of length 6 at a point whose distance from an end of the log is 3.3, resulting in two logs of length 3.3 and 2.7.
In this case, the longest length of a log will be 3.5, which is the shortest possible result. After rounding up to an integer, the output should be 4.
Sample Input 2
3 0 3 4 5
Sample Output 2
5
Sample Input 3
10 10 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202
Sample Output 3
292638192