/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は配送センターで働くスタッフです。配送センターには N 件の届け先があり、それぞれ 1 から N の番号が付けられています。届け先 i には A_i 個の荷物を届ける必要があります。
高橋君は 1 日に 1 つの届け先のみを訪問し、その届け先に最大 K 個の荷物を届けることができます。1 日に届けきれない荷物がある場合は、別の日に同じ届け先を再度訪問して届けます。したがって、届け先 i への配送を完了するには \lceil A_i / K \rceil 日かかり、すべての届け先への配送を完了するために必要な日数は \sum_{i=1}^{N} \lceil A_i / K \rceil 日です。
青木君は配送センターの管理者であり、配送にかかる日数を少しでも短縮したいと考えています。そこで青木君は、配送を開始する前に、1 日あたりの配送能力を増やすことを検討しています。具体的には、青木君は 0 以上 M 以下の整数 x を 1 つ選び、1 日あたりの配送能力を K から K + x に変更することができます。この変更は配送開始前に一度だけ行い、配送中は変えることができません。なお x = 0 を選び、能力を変更しないことも可能です。
青木君が最適に x を選んだとき、高橋君がすべての荷物の配送を完了するために必要な最小の日数を求めてください。
すなわち、0 \le x \le M を満たす整数 x に対して全体の配送日数は
\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
- 1 行目には、届け先の数を表す整数 N、1 日あたりの配送可能個数を表す整数 K、配送能力を増やせる上限を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、各届け先への荷物の個数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
高橋君がすべての荷物の配送を完了するために必要な最小の日数を 1 行で出力せよ。
入力例 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
Score : 300 pts
Problem Statement
Takahashi is a staff member working at a delivery center. The delivery center has N destinations, each numbered from 1 to N. He needs to deliver A_i packages to destination i.
Takahashi can visit only one destination per day and deliver at most K packages to that destination. If there are packages that cannot be delivered in a single day, he visits the same destination again on another day to deliver them. Therefore, completing the delivery to destination i takes \lceil A_i / K \rceil days, and the total number of days required to complete deliveries to all destinations is \sum_{i=1}^{N} \lceil A_i / K \rceil days.
Aoki is the manager of the delivery center and wants to reduce the number of delivery days as much as possible. To this end, Aoki is considering increasing the daily delivery capacity before deliveries begin. Specifically, Aoki can choose an integer x with 0 \leq x \leq M and change the daily delivery capacity from K to K + x. This change is made only once before deliveries start and cannot be altered during the delivery process. Note that choosing x = 0, i.e., not changing the capacity, is also allowed.
Find the minimum number of days required for Takahashi to complete all deliveries when Aoki chooses x optimally.
In other words, for an integer x satisfying 0 \le x \le M, the total number of delivery days is
\sum_{i=1}^{N} \left\lceil \frac{A_i}{K + x} \right\rceil
Output the total number of delivery days when x is chosen to minimize this value.
Constraints
- 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
- All input values are integers.
Input
N K M A_1 A_2 \ldots A_N
- The first line contains three space-separated integers: N representing the number of destinations, K representing the number of packages that can be delivered per day, and M representing the upper limit of the capacity increase.
- The second line contains N space-separated integers A_1, A_2, \ldots, A_N representing the number of packages for each destination.
Output
Output in a single line the minimum number of days required for Takahashi to complete all deliveries.
Sample Input 1
3 3 2 7 3 5
Sample Output 1
4
Sample Input 2
2 5 0 12 8
Sample Output 2
5
Sample Input 3
5 10 100 100 200 50 75 300
Sample Output 3
8
Sample Input 4
10 100 1000000000 1000000000 999999999 500000000 123456789 987654321 100000000 1 999999999 500000001 750000000
Sample Output 4
10
Sample Input 5
1 1 0 1
Sample Output 5
1