A173975.整箱发货
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
一家工厂有 n 批同一种零件,第 i 批原本有 ai 个零件。
工厂准备从中选择至少 k 批发货,并为本次发货统一确定一个正整数 d,表示每个箱子必须装入的零件数量。
为了让各批零件都能整箱装好,工厂可以使用仓库中的备用零件进行补充。备用零件数量充足,对于每一批被选中的零件,可以独立选择:
- 不补充零件;
- 恰好补充 1 个零件。
每批最多补充 1 个零件,不能减少该批的零件数量,也不能把一批中的零件转移到另一批。
补充完成后,每一批被选中的零件都必须单独装箱,并满足:
- 该批零件全部装入箱子,没有剩余;
- 每个箱子恰好装入 d 个零件;
- 该批至少装满一个箱子。
不同批次的零件不能装入同一个箱子。不被选中的批次不参与本次装箱。
请你求出 d 的最大可能值。在上述规则和数据范围下,保证存在满足要求的装箱容量。
输入格式
第一行输入两个整数 n,k,分别表示零件批次数和至少需要选择的批次数。
第二行输入 n 个整数 a1,a2,…,an,表示各批零件的原始数量。
输出格式
输出一个整数,表示每个箱子装入的零件数量 d 的最大可能值。
输入输出样例
输入#1
5 3 5 6 11 17 20
输出#1
6
输入#2
1 1 10
输出#2
11
说明/提示
样例解释 1
当 d=6 时:
- 第 1 批补充 1 个零件后有 6 个,可以装满 1 箱;
- 第 2 批不补充零件,有 6 个,可以装满 1 箱;
- 第 3 批补充 1 个零件后有 12 个,可以装满 2 箱;
- 第 4 批补充 1 个零件后有 18 个,可以装满 3 箱。
因此,能够选择至少 3 批发货。不存在大于 6 的 d 能满足要求,所以答案为 6。
样例解释 2
给唯一的一批零件补充 1 个零件后,共有 11 个零件,可以装满一个容量为 11 的箱子。
数据范围
对于所有测试数据,保证:
- 1≤n≤2×105;
- 1≤k≤n;
- 1≤ai≤106;
- 不同批次的零件数量可以相同。
输入解题思路,AI测评打分。不知道怎么写?