题目描述(ID:12350)
标题: 恢复通讯 (why did the cow cross the road II)
标签: 贪心 模拟
详情:
啊哈星球工业区的一条很长的通讯线路有N个顺序排列的中转站组成,分别编号为1,2…N1<=N<=1000000)。有一天,一场电磁风暴摧毁了B个中转站,使各个区域之间失去了联系。时间紧急,啊哈沃德需要修复一些中转站,使得至少有K个连续的区域恢复通讯。在给定的N,K,B的数值下,计算啊哈沃德最少要修复中转站的数量。
输入格式:
第一行包含三个整数,N,K,B,(1<=N<=1000000),(1<=B,K<=N)。
接下来B行每行中有1个整数,代表毁坏的中转站的编号
输出格式:
计算为了使至少连续K个区域恢复通讯,啊哈沃德至少需要修复多少个中转站
提示: 本题改编自USACO 2017 why did the cow cross the road II
样例:

输入

10 6 5
2
10
1
5
9

输出

1

解释

修复5号中转站,就能够使3,4,5,6,7,8共6个连续的街区恢复通讯
登录并解答