题目描述

It's already 21:30 now, and it's time for BaoBao to go to bed. To ensure his sleeping quality, BaoBao decides to turn all the lights in his bedroom off.

There are $n$ lights, numbered from 1 to $n$, arranged in a row in BaoBao's bedroom. Each time BaoBao can select an integer $i$ and turn all the lights numbered from $i$ to $(i+L-1)$ (both inclusive) off, where $L$ is a predefined positive integer. Note that each time the value of $L$ must be the same.

Given the initial status of all the lights, please help BaoBao determine the smallest possible $L$ so that he can turn all the lights off within $k$ times.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \times 10^5$).

The second line contains a string $s$ ($|s| = n$, $s \in \{\text{`0'}, \text{`1'}\}$) indicating the initial status of the lights. Let $s_i$ be the $i$-th character in $s$, if $s_i = \text{`1'}$ then the $i$-th light is initially on, otherwise it's initially off. It's guaranteed that there is at least one `1· in $s$.

It's guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^6$.

输出格式

For each test case output one line containing one integer, indicating the smallest possible $L$.

题目大意

【题目描述】

现在已经是 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$。

翻译来自于：ChatGPT。

2
10 4
0101011111
3 1
010

3
1