[已解决]求助思路

sfqxx

# [SNCPC2019] 关掉灯

## 题目描述

现在已经是晚上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

### 样例输入 #1

```
2
10 4
0101011111
3 1
010
```

### 样例输出 #1

```
3
1
```

求思路

最佳答案

月排行榜 / 总排行榜

琅琊王朝

2023-9-17 21:35:15

对于这个问题，我们可以采用二分搜索的方法来确定最小可能的L。

首先，我们可以观察到，当L越大时，每次操作熄灭的灯的数量也会越多。因此，我们可以使用二分搜索来找到最小的L。

设定左边界l为1，右边界r为n（灯的数量）。在每一次二分搜索中，我们取mid为左边界和右边界的中间值，并计算需要多少次操作才能熄灭所有的灯。具体计算的过程如下：

1. 初始化变量cnt为0，表示已经进行的操作次数，cur为当前需要熄灭的灯的编号。
2. 从左到右遍历初始状态字符串s：
   - 如果当前灯是开着的（s[i] = '1'），则进行操作：
     - 将cur更新为i + L - 1（即本次操作所熄灭的最后一盏灯的编号）。
     - 将cnt加1。
3. 如果cnt小于等于k，表示当前的L太大了，可以继续减小L，因此将右边界r更新为mid。
4. 否则，表示当前的L太小了，需要增大L，因此将左边界l更新为mid + 1。

重复上述步骤，直到左边界l等于右边界r为止。最终的结果即为l（或r），即最小可能的L。

以下是具体实现的伪代码：

1. function count(l, s, k):
2.     cnt = 0
3.     cur = -1
5.     for i = 0 to n-1:
6.         if s[i] == '1':
7.             if i > cur:
8.                 cnt += 1
9.                 cur = i + l - 1
11.     return cnt
13. function binarySearch(s, k, l, r):
14.     while l < r:
15.         mid = (l + r) / 2
16.         cnt = count(mid, s, k)
18.         if cnt <= k:
19.             r = mid
20.         else:
21.             l = mid + 1
23.     return l
25. # 对每个测试用例进行处理
26. for each test case:
27.     l = 1
28.     r = n
29.     result = binarySearch(s, k, l, r)
30.     print(result)

复制代码

时间复杂度分析：
二分搜索的时间复杂度为O(logn)，在每一次二分搜索中，需要遍历字符串s，所以时间复杂度为O(n)。因此，总的时间复杂度为O(n logn)。

希望以上的思路对你有帮助！如果还有其他问题，请继续提问。
此内容为ChatGPT回答，如果胡说八道，请不要理会
如果对你有帮助，请设置一个最佳答案！

跳转到最佳答案楼层

isdkz

题目描述

有 $n$ 盏灯，编号从 $1$ 到 $n$，排列在一排。每次可以选择一个整数 $i$，将编号从 $i$ 到 $(i+L-1)$（包括两端）的所有灯关掉，其中 $L$ 是一个预先定义的正整数。注意，每次操作中，$L$ 的取值必须相同。给定所有灯的初始状态，请确定最小可能的 $L$，以便在 $k$ 次操作内关闭所有的灯。

解题思路

题目要求我们求最小可能的 $L$，所以可以采用二分答案的思路。假设当前二分的答案是 $mid$，那么我们可以通过贪心的思想来判断是否能在 $k$ 次操作内关闭所有的灯。

具体来说，我们可以从左到右遍历所有的灯，如果当前灯是开着的，那么我们就将它及其后面的 $mid-1$ 盏灯关闭，表示当前操作关闭了这些灯，然后将操作次数 $cnt$ 加 $1$。如果当前操作次数 $cnt$ 大于 $k$，那么说明无法在 $k$ 次操作内关闭所有的灯，此时我们就需要将二分答案 $mid$ 调大，否则就将二分答案 $mid$ 调小。

最后，当二分答案 $mid$ 的值足够小，使得可以在 $k$ 次操作内关闭所有的灯时，此时的 $mid$ 就是最小可能的 $L$。

时间复杂度

二分答案的时间复杂度为 $O(\log n)$，每次二分时需要遍历所有的灯，时间复杂度为 $O(n)$，所以总时间复杂度为 $O(n \log n)$。

参考代码

下面是使用 Python 语言实现的参考代码。

陶远航

这道题目可以使用二分搜索来解决。我们需要找到最小可能的$L$，使得在$k$次操作内关闭所有的灯。

首先，明确一些性质：
· 如果一个灯泡的状态是开着的，那么它之后的$L-1$个灯泡也必须是开着的才能保证在同一次操作内将它们全部关闭。
· 如果某一次操作选择将第$i$个灯泡关闭，那么前面的$i-1$个灯泡中，至少有一个是开着的。

基于以上性质，我们可以进行二分搜索。搜索的区间范围是$[1, n]$，即$L$的取值范围为$1$到$n$。对于每次搜索的中间值$m$，我们判断是否存在一个方案，使得以$L=m$进行操作，将所有的灯关闭。

具体步骤如下：
1. 将初始状态的字符串$s$转换为数组lights，其中lights[ i]表示第i盏灯的状态（0表示关着，1表示开着）。
2. 定义一个辅助函数canTurnOff(lights, k, L)，用于判断以$L$为步长进行操作时，是否可以在$k$次操作内将所有的灯关闭。在该函数中，使用一个变量count记录当前已经关闭的灯的数量。
    · 初始化count为0。
    · 从灯的索引0开始循环至灯的索引n-1。
    · 如果当前灯的状态为1（开着的），则进行以下判断：
        · 如果count小于k，则将count增加1，表示关闭了一个灯。
        · 否则，返回False，表示无法在k次操作内将所有的灯关闭。
    · 如果count小于k，表示在k次操作内可以将所有的灯关闭，返回True。
    · 否则，返回False。
3. 开始二分搜索。初始化左边界left为1，右边界right为n。
4. 当left小于等于right时，进行以下步骤：
    · 计算中间值mid = (left + right) // 2。
    · 调用canTurnOff(lights, k, mid)判断以mid为步长进行操作是否可行。
        · 如果可行，说明当前的mid可能是解，更新右边界为mid-1。
        · 如果不可行，说明当前的mid不是解，更新左边界为mid+1。
5. 最终的解即为左边界left。

通过上述算法，我们可以找到最小可能的$L$，使得在$k$次操作内关闭所有的灯。

希望以上思路对您有所帮助！
如果问题已经解决，请设置最佳答案

琅琊王朝

对于这个问题，我们可以采用二分搜索的方法来确定最小可能的L。

首先，我们可以观察到，当L越大时，每次操作熄灭的灯的数量也会越多。因此，我们可以使用二分搜索来找到最小的L。

设定左边界l为1，右边界r为n（灯的数量）。在每一次二分搜索中，我们取mid为左边界和右边界的中间值，并计算需要多少次操作才能熄灭所有的灯。具体计算的过程如下：

1. 初始化变量cnt为0，表示已经进行的操作次数，cur为当前需要熄灭的灯的编号。
2. 从左到右遍历初始状态字符串s：
   - 如果当前灯是开着的（s[i] = '1'），则进行操作：
     - 将cur更新为i + L - 1（即本次操作所熄灭的最后一盏灯的编号）。
     - 将cnt加1。
3. 如果cnt小于等于k，表示当前的L太大了，可以继续减小L，因此将右边界r更新为mid。
4. 否则，表示当前的L太小了，需要增大L，因此将左边界l更新为mid + 1。

重复上述步骤，直到左边界l等于右边界r为止。最终的结果即为l（或r），即最小可能的L。

以下是具体实现的伪代码：

1. function count(l, s, k):
2.     cnt = 0
3.     cur = -1
5.     for i = 0 to n-1:
6.         if s[i] == '1':
7.             if i > cur:
8.                 cnt += 1
9.                 cur = i + l - 1
11.     return cnt
13. function binarySearch(s, k, l, r):
14.     while l < r:
15.         mid = (l + r) / 2
16.         cnt = count(mid, s, k)
18.         if cnt <= k:
19.             r = mid
20.         else:
21.             l = mid + 1
23.     return l
25. # 对每个测试用例进行处理
26. for each test case:
27.     l = 1
28.     r = n
29.     result = binarySearch(s, k, l, r)
30.     print(result)

复制代码

时间复杂度分析：
二分搜索的时间复杂度为O(logn)，在每一次二分搜索中，需要遍历字符串s，所以时间复杂度为O(n)。因此，总的时间复杂度为O(n logn)。

希望以上的思路对你有帮助！如果还有其他问题，请继续提问。
此内容为ChatGPT回答，如果胡说八道，请不要理会
如果对你有帮助，请设置一个最佳答案！