分数: 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