题目描述

在一条数轴上有 $n$ 个整数点，分别是 $1$ 至 $n$ 。现在已经有 $m$ 个警卫，第 $i$ 个警卫的位置在 $p_i$ 。每个警卫都能看守一段距离 $k$ 。第 $i$ 个警卫能看守的范围从 $p_i-k$ 到 $p_i+k$ 。现在的问题是：至少还需要增加多少个警卫，才能使得 $1$ 至 $n$ 所有的整点都能被警卫看守？注意：你可以把增加的警卫放到任意需要的地方。

输入格式

第 $1$ 行，一个整数 $n$ 。

第 $2$ 行，一个整数 $m$ 。

第 $3$ 行，一个整数 $k$ 。

接下来有 $m$ 行，第 $i$ 行是一个整数 $p_i$ 。所有的警卫的位置都不会重叠。

数据范围

$1 \le n \le 10^9$

$1 \le m \le 10^6$

$0 \le k \le n$

$1 \le p_i \le n$

输出格式

一个整数。

样例

5
2
2
1
5

0

26
3
3
3
19
26

2

完善程序

#include<bits/stdc++.h>
using namespace std;
int n,m,k,p,ans;
int x[1000010];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		scanf("%d",&x[i]);
	}

	x[++m] = __填空(1)__; // 增加一个虚拟的警卫，他能看守到的最左端为 n+1，看守不到位置 n 的 

	sort(x+1,x+1+m);
	
	x[0] = __填空(2)__; // 增加一个虚拟的警卫，他能看到的最右端为 0，不能看守到位置 1 的。 
	
	int d; 
	for(int i=1;i<=m;i++){
		if(x[i]-x[i-1]-1>__填空(3)__){ // 两个警卫之间的不能有多于 2*k 个整数，否则会有一些位置没有人看守
			d = __填空(4)__; // d 为没有人看守的位置
			if(d%(2*k+1)==0)
				ans += __填空(5)__; 
			else
				ans += __填空(6)__;
		}
	}
	cout<<ans;

	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}