#MYD5. 木材加工

木材加工

题目描述

木材厂有 n 根原木,第 i 根长度为 L_i。现在需要把它们切成至少 k 段长度相等的小段(段长必须为正整数,原木只能整段地切,不能拼接),不要求用完所有原木(多余部分舍弃)。输入保证所有原木总长不小于 k。求满足条件的最大段长。

输入格式

第一行两个整数 n 和 k。第二行 n 个整数 L_i。

输出格式

一行一个整数,表示最大段长。若最大段长为 1 也应输出 1。

数据范围

1 ≤ n ≤ 100000,1 ≤ k ≤ 10^9,1 ≤ L_i ≤ 10^9。保证 Σ L_i ≥ k。

样例

3 7
232 124 456
114
3 9
10 20 30
6

说明/提示

二分答案。

解析

思路:二分段长 d,检查 Σ⌊L_i/d⌋ ≥ k 是否成立;d 越大越难满足,具有单调性。上界取 max L_i。

复杂度:O(n log max L)。

来源

人工命题 · 三方对比实验