← 返回题目列表

AtCoder · awc0030_c

C. 交通堵塞报告

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥在高速公路交通控制中心工作,监控交通拥堵情况。

高速公路包括 N 部分排列成行,编号部分 1,部分 2, \ldots,部分 N 从起点开始依次排列。每个路段都有该路段是否拥堵以及路段状态的信息 i 表示为 S_i (S_i = 1 表示拥堵, S_i = 0 表示正常)。

高桥在监视器上检查所有路段的拥堵状况,并针对拥堵路段连续的地方进行报告。

这里,我们定义一个 拥堵块 如下:

A 最大 拥塞部分的连续子序列称为拥塞块。也就是说,当节 l, l+1, \ldots, r (1 \leq l \leq r \leq N) 满足以下所有条件,节中的节组 l 至部分 r 被称为长度的拥塞块 r - l + 1:

  • S_l = S_{l+1} = \cdots = S_r = 1.
  • l = 1 or S_{l-1} = 0.
  • r = N or S_{r+1} = 0.

对于每个拥塞块,高桥做出以下判断:

  • 如果拥塞块的长度是 K 以上,判定为大范围拥堵, 紧急报告 已发给他的主管一次。
  • 如果拥塞块的长度小于 K,按正常流程处理(不生成紧急报告)。

对所有拥塞块进行判断后,确定生成的紧急报告总数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • S_i \in \{0, 1\} (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N K
S_1 S_2 \ldots S_N

第一行包含节数 N 和阈值长度 K 用于需要紧急报告的拥塞区块,以空格分隔。

第二行包含每个部分的状态 S_1, S_2, \ldots, S_N,用空格分隔。 S_i = 1 表示部分 i 很拥堵,并且 S_i = 0 表示正常。

输出

输出单行中生成的紧急报告总数。


样本输入 1

10 3
0 1 1 1 0 1 1 0 1 1

示例输出 1

1

示例输入 2

15 2
1 1 0 1 0 1 1 1 1 0 0 1 1 0 1

示例输出 2

3

示例输入 3

20 4
1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1

示例输出 3

2