#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)。
来源
人工命题 · 三方对比实验