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

    • 79通过
    • 135提交
  • 题目提供者FarmerJohn2
  • 标签 USACO 2017
  • 难度 普及/提高-
  • 时空限制 1s / 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类违反进行处理。