分数: 366 分
问题陈述
在高桥的房间里,有 N 灯排列成水平行,从左到右编号为灯 1,光 2, \ldots,光 N。每个灯都处于两种状态之一:“开”或“关”。每个灯的初始状态由字符串给出 S。如果 i- 第一个字符 S is 1,然后点亮 i 已打开;如果是的话 0,然后点亮 i 已关闭。
高桥想要打开所有的灯。他可以执行以下操作任意次数(包括零次)。
操作: 选择一个整数 l (1 \leq l \leq N - K + 1)并切换所有状态 K 连续亮起灯 l 点亮 l + K - 1。即,打开的灯关闭,关闭的灯打开。的价值 每个操作中选择的 l 是任意的,并且在不同的操作中可以选择相同的值。
判断是否可以打开所有的灯,如果可以,求所需的最少操作次数。
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq K \leq N
- S 是一个长度为的字符串 N 仅包含
0和1 - N, K 是整数
输入
N K S
- 第一行包含一个整数 N 代表灯的数量和一个整数 K 表示一次切换的灯光数量,以空格分隔。
- 第二行包含一个字符串 S 长度 N 代表每个灯的初始状态。
输出
如果可以打开所有的灯,则在一行中输出所需的最少操作次数。如果不可能,则输出 -1.
示例输入 1
5 3 00100
示例输出 1
2
示例输入 2
5 3 01000
示例输出 2
-1
示例输入 3
10 2 0101010101
示例输出 3
-1
示例输入 4
20 5 00000000001111111111
示例输出 4
2
示例输入 5
1 1 1
示例输出 5
0