[SNCPC2019] 关灯(Turn It Off)

题目描述

现在已经是 21:30 了，宝宝该上床睡觉了。为了确保他的睡眠质量，宝宝决定关掉卧室里的所有灯。

宝宝的卧室里有 $n$ 盏灯，从 $1$ 到 $n$ 排成一排。每次宝宝可以选择一个整数 $i$，并将从第 $i$ 盏灯到第 $(i+L-1)$ 盏灯（包括两端）之间的所有灯关掉，其中 $L$ 是一个预定义的正整数。注意，每次操作的 $L$ 值必须相同。

给定所有灯的初始状态，请帮助宝宝确定可能的最小 $L$ 使得他能在 $k$ 次操作内关掉所有的灯。

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \times 10^5$）。

第二行包含一个字符串 $s$（$|s| = n$, $s \in \{\text{`0'}, \text{`1'}\}$）表示灯的初始状态。设 $s_i$ 为字符串 $s$ 的第 $i$ 个字符，如果 $s_i = \text{`1'}$，则第 $i$ 盏灯初始是亮的，否则是灭的。保证 $s$ 中至少有一个 1。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^6$。

输出格式

对于每个测试用例输出一行，包含一个整数，表示可能的最小 $L$。

样例输入 #1

2
10 4
0101011111
3 1
010

样例输出 #1

3
1

数据范围

对于 $100\%$ 的数据，$1 \le k \le n \le 2 \times 10^5$，$\sum n \le 2 \times 10^6$，且每个字符串 $s$ 中至少包含一个 1。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度（CF Rating）：1200。

测试点分布

出处：原题链接