分数: 400 分
问题陈述
高桥有一个装饰面板 N 灯泡排成一排。灯泡编号为 1 to N 从左到右,每个灯泡处于两种状态之一:“开”或“关”。
每个灯泡的初始状态由一个整数给出 A_i。当 A_i = 0,灯泡 i is on,当 A_i = 1,灯泡 i is 关闭.
Takahashi 可以执行以下操作任意次数(可能为零):
- 选择一个整数 i (1 \leq i \leq N - K + 1)并切换灯泡的状态 i, i+1, \ldots, i+K-1。也就是说,这其中 K 连续的灯泡,那些打开的灯泡被关闭,那些关闭的灯泡被打开。
的值 每次操作中选择的 i 每次都可以自由决定,并且允许选择与之前相同的值。
高桥想要打开所有灯泡(即达到 A_i = 0 对于所有人 i)。确定这是否可行,如果可行,请找出所需的最少操作数。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- A_i \in \{0, 1\} (1 \leq i \leq N)
- 所有输入均为整数
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表灯泡数量和一个整数 K 表示一次操作中切换的灯泡数量,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个灯泡的初始状态,以空格分隔。
- 当 A_i = 0,灯泡 i 已打开。
- 当 A_i = 1,灯泡 i 已关闭。
输出
如果可以打开所有灯泡,则在一行中输出所需的最少操作次数。
如果不可能,则输出 -1 一行。
示例输入 1
5 3 0 1 1 1 0
示例输出 1
1
示例输入 2
4 2 1 0 0 1
示例输出 2
3
示例输入 3
10 3 1 1 1 0 0 0 1 1 1 0
示例输出 3
2