A15830 | Vaccination
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Ethan runs a vaccination station to help people combat the seasonal flu. He analyses the historical data in order to develop an optimal strategy for vaccine usage.
Consider there are $n$ patients coming to the station on a particular day. The $i$ -th patient comes at the moment $t_i$ . We know that each of these patients can be asked to wait for no more than $w$ time moments. That means the $i$ -th patient can get vaccine at moments $t_i, t_i + 1, \ldots, t_i + w$ .
Vaccines come in packs, each pack consists of $k$ doses. Each patient needs exactly one dose. Packs are stored in a special fridge. After a pack is taken out of the fridge and opened, it can no longer be put back. The lifetime of the vaccine outside the fridge is $d$ moments of time. Thus, if the pack was taken out of the fridge and opened at moment $x$ , its doses can be used to vaccinate patients at moments $x, x + 1, \ldots, x + d$ . At moment $x + d + 1$ all the remaining unused doses of this pack are thrown away.
Assume that the vaccination station has enough staff to conduct an arbitrary number of operations at every moment of time. What is the minimum number of vaccine packs required to vaccinate all $n$ patients?
Consider there are $n$ patients coming to the station on a particular day. The $i$ -th patient comes at the moment $t_i$ . We know that each of these patients can be asked to wait for no more than $w$ time moments. That means the $i$ -th patient can get vaccine at moments $t_i, t_i + 1, \ldots, t_i + w$ .
Vaccines come in packs, each pack consists of $k$ doses. Each patient needs exactly one dose. Packs are stored in a special fridge. After a pack is taken out of the fridge and opened, it can no longer be put back. The lifetime of the vaccine outside the fridge is $d$ moments of time. Thus, if the pack was taken out of the fridge and opened at moment $x$ , its doses can be used to vaccinate patients at moments $x, x + 1, \ldots, x + d$ . At moment $x + d + 1$ all the remaining unused doses of this pack are thrown away.
Assume that the vaccination station has enough staff to conduct an arbitrary number of operations at every moment of time. What is the minimum number of vaccine packs required to vaccinate all $n$ patients?
输入格式
The first line of the input contains the number of test cases $t$ ( $1 \leq t \leq 10^4$ ). Then follow $t$ descriptions of the test cases.
The first line of each test case contains four integers $n$ , $k$ , $d$ and $w$ ( $1 \leq n, k \leq 2 \cdot 10^5$ , $0 \leq d, w \leq 10^6$ ). They are the number of patients, the number of doses per vaccine pack, the number of moments of time the vaccine can live outside the fridge, and the number of moments of time each of the patients can wait, respectively.
The second line of each test case contains a non-decreasing sequence $t_1, t_2, \ldots, t_n$ ( $0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^6$ ). The $i$ -th element of this sequence is the moment when the $i$ -th patient comes to the vaccination station.
It is guaranteed that the sum of $n$ over all test cases won't exceed $2 \cdot 10^5$ .
The first line of each test case contains four integers $n$ , $k$ , $d$ and $w$ ( $1 \leq n, k \leq 2 \cdot 10^5$ , $0 \leq d, w \leq 10^6$ ). They are the number of patients, the number of doses per vaccine pack, the number of moments of time the vaccine can live outside the fridge, and the number of moments of time each of the patients can wait, respectively.
The second line of each test case contains a non-decreasing sequence $t_1, t_2, \ldots, t_n$ ( $0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^6$ ). The $i$ -th element of this sequence is the moment when the $i$ -th patient comes to the vaccination station.
It is guaranteed that the sum of $n$ over all test cases won't exceed $2 \cdot 10^5$ .
输出格式
Output one integer, the minimum number of vaccine packs required to vaccinate all $n$ patients.
输入输出样例
输入 #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
In the first example, the first pack can be opened at moment $1$ to vaccinate patient $1$ . The vaccine is durable enough to be used at moments $2$ and $3$ for patients $2$ and $3$ , respectively. Then the staff needs to ask patients $4$ and $5$ to wait for moment $13$ . At moment $13$ the staff opens the second vaccine pack and serves patients $4$ and $5$ . Finally, the last patient comes at moment $18$ and immediately gets the last dose of the second pack while it is still fine.
In the second example, the vaccine should be used exactly at the moment it is taken out of the fridge. Moreover, all the patients want to be served at exactly the same moment they come. That means the staff needs to open two packs at moment $3$ and use five doses on patients $1$ , $2$ , $3$ , $4$ , and $5$ . There will be three doses left ouf of these two packs but they can't be used for patient $6$ . When patient $6$ comes at moment $4$ the staff needs to open a new pack just to use only one dose out of it.
In the second example, the vaccine should be used exactly at the moment it is taken out of the fridge. Moreover, all the patients want to be served at exactly the same moment they come. That means the staff needs to open two packs at moment $3$ and use five doses on patients $1$ , $2$ , $3$ , $4$ , and $5$ . There will be three doses left ouf of these two packs but they can't be used for patient $6$ . When patient $6$ comes at moment $4$ the staff needs to open a new pack just to use only one dose out of it.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted