A16120 | The Walkway
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
There are $n$ benches near the Main Walkway in Summer Infomatics School. These benches are numbered by integers from $1$ to $n$ in order they follow. Also there are $m$ cookie sellers near the Walkway. The $i$ -th ( $1 \le i \le m$ ) cookie sellers is located near the $s_i$ -th bench.
Petya is standing in the beginning of the Walkway. He will pass near all benches starting from the $1$ -st bench and ending with the $n$ -th bench. Petya passes the distance between two consecutive benches in $1$ minute. He has a knapsack with an infinite amount of cookies. Petya is going to eat cookies from his knapsack and buy them from cookie sellers during the walk.
Petya eats cookies only near the benches according to the following rule: he will eat the cookie near the $i$ -th ( $1 \le i \le n$ ) bench if and only if at least one of the following conditions holds:
- There is a cookie seller near the $i$ -th bench. Then Petya will buy a cookie from cookie seller and eat it immediately.
- Petya has not yet eaten a cookie. Then Petya will take a cookie from his knapsack and eat it immediately.
- At least $d$ minutes passed since Petya ate the previous cookie. In other words, Petya has not eaten a cookie near the benches $i-1, i-2, \ldots, \max(i-d+1, 1)$ . Then Petya will take a cookie from his knapsack and eat it immediately.
You may assume that Petya eats cookies instantly. Petya will not eat two or more cookies near the same bench.
You want to minimize the number of cookies Petya will eat during his walk. In order to do this, you will ask the administration of the Summer Informatics School to remove exactly one cookie seller from the Walkway before Petya starts his walk.
Please determine the minimum possible number of cookies Petya can eat after removing exactly one cookie seller. Also determine the number of cookie sellers, such that if you remove one of them, Petya will eat the minimum possible number of cookies.
Petya is standing in the beginning of the Walkway. He will pass near all benches starting from the $1$ -st bench and ending with the $n$ -th bench. Petya passes the distance between two consecutive benches in $1$ minute. He has a knapsack with an infinite amount of cookies. Petya is going to eat cookies from his knapsack and buy them from cookie sellers during the walk.
Petya eats cookies only near the benches according to the following rule: he will eat the cookie near the $i$ -th ( $1 \le i \le n$ ) bench if and only if at least one of the following conditions holds:
- There is a cookie seller near the $i$ -th bench. Then Petya will buy a cookie from cookie seller and eat it immediately.
- Petya has not yet eaten a cookie. Then Petya will take a cookie from his knapsack and eat it immediately.
- At least $d$ minutes passed since Petya ate the previous cookie. In other words, Petya has not eaten a cookie near the benches $i-1, i-2, \ldots, \max(i-d+1, 1)$ . Then Petya will take a cookie from his knapsack and eat it immediately.
You may assume that Petya eats cookies instantly. Petya will not eat two or more cookies near the same bench.
You want to minimize the number of cookies Petya will eat during his walk. In order to do this, you will ask the administration of the Summer Informatics School to remove exactly one cookie seller from the Walkway before Petya starts his walk.
Please determine the minimum possible number of cookies Petya can eat after removing exactly one cookie seller. Also determine the number of cookie sellers, such that if you remove one of them, Petya will eat the minimum possible number of cookies.
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 10^3$ ) — the number of test cases.
The first line of each test case contains three integers $n$ , $m$ and $d$ ( $2 \le d \le n \le 10^9$ , $2 \le m \le \min(10^{5}, n)$ ) — the number of benches, the number of cookie sellers and the value of parameter $d$ from the statement, respectively.
The second line of each test case contains $m$ integers $s_1, s_2, \ldots, s_m$ ( $1 \le s_i \le n$ ) — the locations of the cookie sellers. It is guaranteed that $s_{i} < s_{i+1}$ for all $1 \leq i \leq m - 1$ .
It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$ .
The first line of each test case contains three integers $n$ , $m$ and $d$ ( $2 \le d \le n \le 10^9$ , $2 \le m \le \min(10^{5}, n)$ ) — the number of benches, the number of cookie sellers and the value of parameter $d$ from the statement, respectively.
The second line of each test case contains $m$ integers $s_1, s_2, \ldots, s_m$ ( $1 \le s_i \le n$ ) — the locations of the cookie sellers. It is guaranteed that $s_{i} < s_{i+1}$ for all $1 \leq i \leq m - 1$ .
It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$ .
输出格式
For each test case print two integers — the minimum number of cookies that Petya can eat if exactly one cookie seller is removed, and the number of cookie sellers such that if one of them is removed, Petya will eat the minimum possible number of cookies.
输入输出样例
输入 #1
8 6 2 2 2 5 8 3 2 3 5 8 10 4 9 2 8 9 10 30 5 8 6 8 15 24 29 30 5 8 6 8 12 20 27 8 8 3 1 2 3 4 5 6 7 8 2 2 2 1 2 1000000000 3 20000000 57008429 66778899 837653445
输出 #1
3 1 4 1 4 4 6 4 5 2 7 7 1 1 51 1
In the first test case $n=6$ , $m=2$ , $d=2$ and $s=[2, 5]$ . If no cookie seller is removed, then Petya will eat $4$ cookies during his walk (note that you have to remove exactly one cookie seller; this case is explained only to show how Petya decides whether to eat a cookie):
- Petya will eat a cookie near the $1$ -st bench since he has not yet eaten a cookie.
- Petya will eat a cookie near the $2$ -nd bench since there is a cookie seller near this bench.
- Petya will not eat a cookie near the $3$ -rd bench since only $1<d$ minute passed since he ate a cookie.
- Petya will eat a cookie near the $4$ -th bench since $2\ge d$ minutes passed since he ate a cookie.
- Petya will eat a cookie near the $5$ -th bench since there is a cookie seller near this bench.
- Petya will not eat a cookie near the $6$ -th bench since only $1<d$ minute passed since he ate a cookie.
If the $1$ -st cookie seller is removed, Petya will eat $3$ cookies (near the benches $1$ , $3$ and $5$ ). If the $2$ -nd cookie seller is removed, Petya will eat $4$ cookies (near the benches $1$ , $2$ , $4$ and $6$ ).
Thus, the minimum number of cookies Petya will eat is $3$ ; there is only one cookie seller such that removing it results in minimizing the number of cookies Petya will eat.
In the second test case
- the removal of the $1$ -st or the $2$ -nd cookie seller results in Petya eating $5$ cookies near the benches $1$ , $3$ , $5$ , $7$ , $8$ ;
- the removal of the $3$ -rd cookie seller results in Petya eating $4$ cookies near the benches $1$ , $3$ , $5$ , $7$ .
Note that the second integer you should output is the number of (that is, amount) cookie sellers, not the index of a cookie seller to remove. Thus, the answer to the second test case is 4 1 because there is only one cookie seller such that removing it results in Petya eating four cookies, which is the minimum possible.
In the third test case Petya will eat $4$ cookies no matter what cookie seller is removed.
Note that Petya is not interested in minimizing the number of cookies he will eat, so he eats cookies whenever it is possible under the rule from the statement.
- Petya will eat a cookie near the $1$ -st bench since he has not yet eaten a cookie.
- Petya will eat a cookie near the $2$ -nd bench since there is a cookie seller near this bench.
- Petya will not eat a cookie near the $3$ -rd bench since only $1<d$ minute passed since he ate a cookie.
- Petya will eat a cookie near the $4$ -th bench since $2\ge d$ minutes passed since he ate a cookie.
- Petya will eat a cookie near the $5$ -th bench since there is a cookie seller near this bench.
- Petya will not eat a cookie near the $6$ -th bench since only $1<d$ minute passed since he ate a cookie.
If the $1$ -st cookie seller is removed, Petya will eat $3$ cookies (near the benches $1$ , $3$ and $5$ ). If the $2$ -nd cookie seller is removed, Petya will eat $4$ cookies (near the benches $1$ , $2$ , $4$ and $6$ ).
Thus, the minimum number of cookies Petya will eat is $3$ ; there is only one cookie seller such that removing it results in minimizing the number of cookies Petya will eat.
In the second test case
- the removal of the $1$ -st or the $2$ -nd cookie seller results in Petya eating $5$ cookies near the benches $1$ , $3$ , $5$ , $7$ , $8$ ;
- the removal of the $3$ -rd cookie seller results in Petya eating $4$ cookies near the benches $1$ , $3$ , $5$ , $7$ .
Note that the second integer you should output is the number of (that is, amount) cookie sellers, not the index of a cookie seller to remove. Thus, the answer to the second test case is 4 1 because there is only one cookie seller such that removing it results in Petya eating four cookies, which is the minimum possible.
In the third test case Petya will eat $4$ cookies no matter what cookie seller is removed.
Note that Petya is not interested in minimizing the number of cookies he will eat, so he eats cookies whenever it is possible under the rule from the statement.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted