← 返回题目列表

Codeforces · 1804/B

B. 疫苗接种

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

伊森经营着一个疫苗接种站,帮助人们对抗季节性流感。他分析历史数据,以制定疫苗使用的最佳策略。

考虑在某一天有 $$$n$$$ 名患者来到车站。第 $$$i$$$ 位患者此时来到$$$t_i$$$。我们知道,可以要求每个患者等待不超过 $$$w$$$ 时间。这意味着第 $$$i$$$ 患者可以在 $$$t_i, t_i + 1, \ldots, t_i + w$$$ 时刻接种疫苗。

疫苗有包装,每包包含 $$$k$$$ 剂量。每个患者只需要一剂。包装存放在特殊的冰箱中。包装从冰箱中取出并打开后,就无法再放回去。疫苗在冰箱外的保质期为 $$$d$$$ 时刻。因此,如果将包装从冰箱中取出并在 $$$x$$$ 时刻打开,则其剂量可用于在 $$$x, x + 1, \ldots, x + d$$$ 时刻为患者接种疫苗。此时,$$$x + d + 1$$$ 该包中所有剩余未使用的剂量都将被丢弃。

假设疫苗接种站有足够的工作人员,可以在每个时刻进行任意数量的操作。为所有 $$$n$$$ 患者接种疫苗所需的最少疫苗包数量是多少?

输入

输入的第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。然后遵循测试用例的 $$$t$$$ 描述。

每个测试用例的第一行包含四个整数 $$$n$$$、$$$k$$$、$$$d$$$ 和 $$$w$$$ ($$$1 \leq n, k \leq 2 \cdot 10^5$$$, $$$0 \leq d, w \leq 10^6$$$)。它们分别是患者人数、每包疫苗的剂量数、疫苗在冰箱外可以保存的时间以及每个患者可以等待的时间。

每个测试用例的第二行包含一个非递减序列 $$$t_1, t_2, \ldots, t_n$$$ ($$$0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^6$$$)。该序列的第 $$$i$$$ 个元素是第 $$$i$$$ 个患者到达疫苗接种站的时刻。

保证所有测试用例的 $$$n$$$ 总和不会超过 $$$2 \cdot 10^5$$$。

输出

输出一个整数,即为所有 $$$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

2
3
2
3
1

注意

在第一个示例中,可以在 $$$1$$$ 时刻打开第一个包来为患者 $$$1$$$ 接种疫苗。该疫苗足够耐用,可以在 $$$2$$$ 和 $$$3$$$ 时刻分别用于 $$$2$$$ 和 $$$3$$$ 患者。然后工作人员需要要求患者$$$4$$$和$$$5$$$等待$$$13$$$。在 $$$13$$$ 时刻,工作人员打开第二包疫苗并为患者提供 $$$4$$$ 和 $$$5$$$ 服务。最后,最后一位患者在 $$$18$$$ 时刻到来,并立即服用了第二包的最后一剂,同时还没有问题。

在第二个示例中,疫苗应在从冰箱中取出时立即使用。此外,所有患者都希望在同一时刻得到服务。这意味着工作人员需要同时打开两包 $$$3$$$ 并对患者使用五剂 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$ 和 $$$5$$$。这两个包中还剩下三剂,但不能用于患者 $$$6$$$。当患者 $$$6$$$ 在 $$$4$$$ 到来时,工作人员需要打开一个新包装,以便只使用其中的一剂。