• 应用
• 登录
• 注册

P3662 [USACO17FEB]Why Did the Cow Cross the Road II S

• 130通过
• 238提交
• 题目提供者 FarmerJohn2
• 评测方式 云端评测
• 标签 前缀和 枚举,暴力 队列 USACO 2017
• 难度 普及/提高-
• 时空限制 1000ms / 128MB
• 提示：收藏到任务计划后，可在首页查看。

题目描述

The long road through Farmer John's farm has $N$ crosswalks across it, conveniently numbered $1 \ldots N$ ( $1 \leq N \leq 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个编号连续的信号灯。

输入输出格式

输入格式：

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

输出格式：

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.

输入输出样例

输入样例#1： 复制
10 6 5
2
10
1
5
9
输出样例#1： 复制
1

说明

感谢@ jlyzxxm1 提供题意简述

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。