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类违反进行处理。