← 返回题目列表

AtCoder · awc0032_b

B. 包裹递送时间表

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥是一名在配送中心工作的工作人员。配送中心有 N 目的地,每个编号自 1 to N。他需要交付 A_i 包裹已发往目的地 i.

高桥每天只能前往一个目的地,最多可送货 K 包裹到该目的地。如果有一天无法送达的包裹,他会改天再去同一目的地递送。因此,完成运送至目的地 i 需要 \lceil A_i / K \rceil 天,完成向所有目的地交货所需的总天数为 \sum_{i=1}^{N} \lceil A_i / K \rceil 天。

Aoki 是配送中心的经理,他希望尽可能减少配送天数。为此,青木正在考虑在发货前增加每日发货能力。具体来说,Aoki可以选择一个整数 x 与 0 \leq x \leq M 并将每日交付能力从 K to K + x。此更改仅在交付开始前进行一次,并且在交付过程中无法更改。注意选择 x = 0,即不改变容量,也是允许的。

求青木选择时高桥完成所有交货所需的最少天数 x 最佳。

换句话说,对于一个整数 x 满意 0 \le x \le M,总交货天数为

\sum_{i=1}^{N} \left\lceil \frac{A_i}{K + x} \right\rceil

输出当 选择 x 来最小化该值。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 0 \leq M \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

N K M
A_1 A_2 \ldots A_N
  • 第一行包含三个空格分隔的整数: N 代表目的地数量, K 代表每天可以投递的包裹数量,以及 M 代表容量增加的上限。
  • 第二行包含 N 空格分隔的整数 A_1, A_2, \ldots, A_N 代表每个目的地的包裹数量。

输出

在一行中输出高桥完成所有交货所需的最少天数。


示例输入 1

3 3 2
7 3 5

示例输出 1

4

示例输入 2

2 5 0
12 8

示例输出 2

5

示例输入 3

5 10 100
100 200 50 75 300

示例输出 3

8

示例输入 4

10 100 1000000000
1000000000 999999999 500000000 123456789 987654321 100000000 1 999999999 500000001 750000000

示例输出 4

10

示例输入 5

1 1 0
1

示例输出 5

1