题目描述

在一条数轴上有 $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;
struct zone{
	int l,r;
}x[1000001];
bool cmp(zone i,zone j)
{
	if(i.l==j.l)
		return i.r<j.r;
	else
		return 填空(1);
}
int n,m,k,p;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&p);
		x[i].l = max(1,p-k);
		x[i].r = 填空(2);
	}
	sort(x+1,填空(3),cmp);
	x[++m].l= 填空(4);
	
	int R=0,ans=0;
	for(int i=1;i<=m;i++)
	{
		if(x[i].l<=R+1)
			R = 填空(5);
		else{
			if((x[i].l-R-1)%(2*k+1)==0)
				ans += 填空(6);
			else
				ans += 填空(7);
			
			R = 填空(8);
		}
	}
	cout<<ans;	

	return 0;
}

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

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

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

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

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

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

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

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