A173975.整箱发货

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

一家工厂有 nn 批同一种零件,第 ii 批原本有 aia_i 个零件。

工厂准备从中选择至少 kk 批发货,并为本次发货统一确定一个正整数 dd,表示每个箱子必须装入的零件数量。

为了让各批零件都能整箱装好,工厂可以使用仓库中的备用零件进行补充。备用零件数量充足,对于每一批被选中的零件,可以独立选择:

  • 不补充零件;
  • 恰好补充 11 个零件。

每批最多补充 11 个零件,不能减少该批的零件数量,也不能把一批中的零件转移到另一批。

补充完成后,每一批被选中的零件都必须单独装箱,并满足:

  • 该批零件全部装入箱子,没有剩余;
  • 每个箱子恰好装入 dd 个零件;
  • 该批至少装满一个箱子。

不同批次的零件不能装入同一个箱子。不被选中的批次不参与本次装箱。

请你求出 dd 的最大可能值。在上述规则和数据范围下,保证存在满足要求的装箱容量。

输入格式

第一行输入两个整数 n,kn,k,分别表示零件批次数和至少需要选择的批次数。

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示各批零件的原始数量。

输出格式

输出一个整数,表示每个箱子装入的零件数量 dd 的最大可能值。

输入输出样例

  • 输入#1

    5 3
    5 6 11 17 20

    输出#1

    6
  • 输入#2

    1 1
    10

    输出#2

    11

说明/提示

样例解释 1

当 d=6d=6 时:

  • 第 11 批补充 11 个零件后有 66 个,可以装满 11 箱;
  • 第 22 批不补充零件,有 66 个,可以装满 11 箱;
  • 第 33 批补充 11 个零件后有 1212 个,可以装满 22 箱;
  • 第 44 批补充 11 个零件后有 1818 个,可以装满 33 箱。

因此,能够选择至少 33 批发货。不存在大于 66 的 dd 能满足要求,所以答案为 66。

样例解释 2

给唯一的一批零件补充 11 个零件后,共有 1111 个零件,可以装满一个容量为 1111 的箱子。

数据范围

对于所有测试数据,保证:

  • 1≤n≤2×1051\le n\le 2\times 10^5;
  • 1≤k≤n1\le k\le n;
  • 1≤ai≤1061\le a_i\le 10^6;
  • 不同批次的零件数量可以相同。

输入解题思路,AI测评打分。不知道怎么写?

首页