J3 习题-5 木屋搭建

题目描述

小喵的农场堆放着 $N$ 根长度为 $l_1$,$l_2$,...,$l_N$ 的原木。今天，小喵准备用这些原木来搭建一间小木屋，用作存放农场冬天的干草。

由于小喵的体力有限，他最多能进行 $K$ 次切割操作，每次他可以选取某根长度为 $L$ 的原木在 $x(0<x<L)$ 的位置进行切割，将原木切为长度为 $x$ 和 $L-x$ 的两根。

为了符合小喵的设计，他需要知道切割后最长那根原木最短为多少。

输入格式

共 $2$ 行： 第一行个两个整数 $N,K$ ，依次表示原木的数量和最多的切割次数； 第二行 $N$ 个整数 $l_i$ ，依次表示第 $i$ 根原木的长度。

输出格式

一行一个整数，输出切割后最长那根原木最短为多少。

样例输入1

2 3
7 9

样例输出1

4

样例输入2

1 4784
450968417

样例输出2

94247

样例输入3

7 996517963
272503281 385111446 560895033 742625617 115928149 113486455 918393042

样例输出3

4

样例说明

样例1

第 $1$ 次切割：将长度为 $7$ 的原木切成长度为 $3.5+3.5$ 的两段； 第 $2$ 次切割：将长度为 $9$ 的原木切成长度为 $3+6$ 的两段； 第 $3$ 次切割：将长度为 $6$ 的原木切成长度为 $3.3+2.7$ 的两段； 这样最长的原木长为 $3.5$ ，是所有切法中最短的，输出 $4$ 。

数据范围

对于 $100 \%$ 的数据：$1\leq N\leq 2\times 10^5,0\leq K\leq 10^9,1\leq l_i\leq 10^9$ ；保证所有输入都是整数。