文字教学

这道题可以用二分查找 + 贪心解决：

1. 二分查找L：因为L越大，需要的操作次数越少，存在单调性，所以找最小的可行L。
2. 判断L是否可行：用贪心策略，从左到右扫，遇到亮着的且未被之前操作覆盖的灯，就从该位置开始关灯（操作[i, i+L-1]），并记录当前操作覆盖的最右位置。统计操作次数是否≤k。
   • 为什么这样贪心？因为左边的灯已经处理完了，不能再回头，所以遇到必须关的灯，只能从这里开始关，这样能覆盖最多的右边的灯，操作次数最少。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
char s[N];
int n, k;

bool check(int L) {
    int op = 0, cov = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '1' && i > cov) {
            op++;
            if (op > k) return false;
            cov = i + L - 1;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k >> (s + 1);
        int l = 1, r = n, ans = n;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}