2838: 随意发糖的 LEEZ(语法周赛 Round 14（思维场）)

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：19 解决：2

题目描述

LEEZ 老师有 n 个学生，这些学生排成了一排，编号从 1\sim n。第 i 个学生有 a_i 颗糖。

LEEZ 老师希望让每个学生都至少有 m 颗糖。初始的所有 a_i 都小于 m。因此，他需要给学生发糖。

LEEZ 老师的发糖方式比较特殊，每次他可以任意挑选一个长度为 k 的区间（比如 a_1\sim a_k 或 a_3\sim a_{k+2}），并发出 num 颗糖，这些糖可以随意分配给区间内的所有学生。

请问 LEEZ 老师最少需要发几次才能让所有学生都至少有 m 颗糖。

输入

第一行四个整数 n,m,k,num。
接下来一行 n 个整数，a_1\sim a_n。

输出

一行一个整数，表示答案。

样例输入 复制 

4 10 2 6
1 2 3 4

样例输出 复制 

5

提示

4 10 2 6
1 2 3 4 
5 
4 10 2 100
1 2 3 4 
2

样例 1 解释

  • 第一步：给 [1 2] 3 4 发，变成 [7 2] 3 4
  • 第二步：给 [7 2] 3 4 发，变成 [10 5] 3 4
  • 第三步：给 10 [5 3] 4 发，变成 10 [10 4] 4
  • 第四步：给 10 10 [4 4] 发，变成 10 10 [7 7]
  • 第五步：给 10 10 [4 4] 发，变成 10 10 [10 10]

数据规模与约定

对于 100\% 的数据，1\le n,m,k,num,a_i \le 5000 且 k\le n，a_i\lt m。

  • 子任务 1（30 分）：保证 num=1
  • 子任务 2（30 分）：保证 k=1
  • 子任务 3（40 分）：没有特殊限制

来源/分类

提交提交记录统计露一手!