← 返回比赛

已结束 GESP欢乐赛 #3

← 上一题下一题 →

A1423 | $疫苗接种$

来源官方 / 2023

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

$AC$ 狗经营着一个疫苗接种站，帮助人们对抗流感病毒。 在某一天有 $n$ 个病人来到了医院。第 $i$ 名患者会在 $t_i$ 时刻来到医院，每一位患者都要求接种疫苗的等待时间不能超过 $w$ 分钟，这意味着第 $i$ 名患者在 $t_i$、$t_i+1$ ......、$t_i+w$ 时刻可接种疫苗。 疫苗是一包一包的，每包由 $k$ 剂疫苗组成。每个病人只需要一剂。包装存放在一个特殊的冰箱里。一包疫苗从冰箱里拿出来打开后，就不能再放回去了。疫苗在冰箱外的寿命是 $d$ 分钟。因此，如果一包疫苗在 $x$ 时刻从冰箱中取出并打开，可以用于在 $x$、$x+1$、\dots、$x+d$ 时刻为患者接种。在 $x+d+1$ 时刻，该包装的所有剩余未使用剂量都被扔掉了。 假设疫苗接种站有足够的工作人员在每个时刻进行任意数量的疫苗接种。为所有 $n$ 名患者接种疫苗所需的最低疫苗包数是多少？

输入格式

输入的第一行 $T$（$1 \le t \le 10^3$），表示有 $T$ 个测试用例。 每一个测试用例的第一行包含四个整数：$n$、$k$、$d$ 和 $w$ （$1 \le n,k \le 10^4$，$0 \le d,w \le 10^6$）。分别表示患者人数、每包疫苗的剂量、疫苗在冰箱外可以存活的时间和每个患者可以等待的时间。 每个测试用例的第二行包含一个非递减序列 $t_1$，$t_2$，…，$t_n$（$0$ $\le t_1$ $\le t_ 2 \le$ …$\le t_n \le 10^6$）。该序列的第 $i$ 个元素是第 $i$ 名患者来到疫苗接种站的时刻。

输出格式

对于每个测试用例输出一个整数，为这 $n$ 名患者接种疫苗所需的最小疫苗包数。

输入输出样例

输入 #1

5
6 3 5 3
1 2 3 10 11 18
6 4 0 0
3 3 3 3 3 4
9 10 2 2
0 1 2 3 4 5 6 7 8
3 10 3 6
10 20 30
5 5 4 4
0 2 4 6 8

输出 #1

C++ 编辑器

输入

输出