A21224.Facer的工厂

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Facer 是一个工厂里的兼职工人,这回他碰到了一个问题。

NN 根钢管,每根长度是 aia_i

有一个钢管加工器,每秒钟可以加工 kk 长度的钢管。

Facer 需要按顺序加工这些钢管。

不过呢,机器的最大等待长度是 hh,即等待加工(已经塞入机器却还没有加工的钢管)的钢管长度不能超过 hh(保证 aiha_i \le h)。

Facer 只能在整数秒的时候塞入钢管。

求 Facer 处理完这些钢管最少要多久呢?

输入格式

第一行 N,H,KN,H,K,代表钢管条数,最大等待长度和每秒处理速度。

接下来 NN 行,每行一个数,代表钢管的长度。

钢管需要按顺序处理。

输出格式

最短时间

输入输出样例

  • 输入#1

    1 5 3
    5

    输出#1

    2
  • 输入#2

    5 6 3
    5 4 3 2 1

    输出#2

    5

说明/提示

样例 1 解释:只有 11 根钢管,加工时间为 5/3=2\lfloor 5/3\rfloor = 2

样例 2 解释:

第一秒塞入 55,等待长度 55,机器处理了 33,等待长度 22

第二秒塞入 44,等待长度 66,机器处理了 33,等待长度 33

第三秒塞入 33,等待长度 66,机器处理了 33,等待长度 33

第四秒塞入了 1,21,2,等待长度 66,机器处理了 33,等待长度 33

第五秒无塞入,等待长度 33,机器处理了 33,处理完毕。

N100000N \le 100000h,ai109h,a_i \le 10^9

首页