题目描述

The long road through Farmer John's farm has N crosswalks across it, conveniently numbered 1…N(1≤N≤100,000). To allow cows to cross at these crosswalks, FJ installs electric crossing signals, which light up with a green cow icon when it is ok for the cow to cross, and red otherwise. Unfortunately, a large electrical storm has damaged some of his signals. Given a list of the damaged signals, please compute the minimum number of signals that FJ needs to repair in order for there to exist some contiguous block of at least K working signals.

题目大意：

共有N个信号灯，编号为1~N，有B个信号灯损坏，给你它们的编号。

问，最少修好几个信号灯，可以有K个编号连续的信号灯。

INPUT FORMAT (file maxcross.in):

The first line of input contains N, K, and B (1≤B,K≤N). The next B lines each describe the ID number of a broken signal.

OUTPUT FORMAT (file maxcross.out):

Please compute the minimum number of signals that need to be repaired in order for there to be a contiguous block of K working signals somewhere along the road.

SAMPLE INPUT:

10 6 5
2
10
1
5
9

SAMPLE OUTPUT:

1

题目来源

USACO 2017 February Contest, Silver

Problem 2. Why Did the Cow Cross the Road II

Problem credits: Brian Dean