Why Did the Cow Cross the Road II

题目描述

Farmer John 的农场中有一条很长的道路，沿路共有 $N$ 个斑马线，方便起见编号为 $1 \ldots N$（$1 \leq N \leq 100,000$）。为了让奶牛能在这些斑马线处过马路，FJ 安装了电动过街信号灯：当可以过街时会亮起绿色奶牛图标，否则为红色。 不幸的是，一场强烈的雷暴损坏了其中一些信号灯。给定损坏信号灯的列表，请计算 FJ 至少需要修理多少个信号灯，才能使得道路上存在某一段长度至少为 $K$ 的连续信号灯全部正常工作。

输入格式

输入格式（文件 maxcross.in）： 第一行包含 $N$、$K$ 和 $B$（$1 \leq B, K \leq N$）。 接下来 $B$ 行每行给出一个损坏信号灯的编号。

输出格式

输出格式（文件 maxcross.out）： 请计算最少需要修理多少个信号灯，才能使得道路上某处存在一段长度为 $K$ 的连续信号灯全部正常工作。

10 6 5
2
10
1
5
9

1

提示

题目致谢：Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver