← 返回题目列表

AtCoder · awc0022_d

D. 灯泡面板的同步控制

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

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