Responsive image

问题 2868 --切割原木(二分)

2868: 切割原木(二分)

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

木材厂有n根原木,现在想把这些木头切割成k段长度为L的小段木头(木头有可能有剩余)。
当然,我们希望得到的小段木头越长越好,请求出L的最大值。
木头长度的单位是cm,原木的长度都是正整数,我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为11和22,要求切割成等长的6段,很明显能切割出来的小段木头长度最长为5

输入描述

第一行是两个正整数n,k,分别表示原木的数量,需要得到的小段的数量。
接下来n行,每行一个正整数 Li,表示一根原木的长度。

输出描述

仅一行,即L的最大值。
如果连1cm长的小段都切不出来,输出0。

样例输入

3 7
232
124
456

样例输出

114

提示

对于100%的数据,有1≤n≤105,1 ≤k≤108,1 ≤Li≤108(i∈[1, n])。

来源

[提交][状态]
ACM算法攻关部