[SNCPC2019] 关灯(Turn It Off) 题解

思路分析

固定操作长度 $L$ 时，从左到右扫描字符串，每遇到一盏亮着的灯 1（下标 $i$），贪心地覆盖 $[i, i + L - 1]$ 最优，随后直接跳到 $i + L$ 继续扫描。所需操作次数随 $L$ 增大单调不增，因此在 $[1, n]$ 上二分答案 $L$ 即可。单组数据时间复杂度 $O(n \log n)$。

参考代码

#include <iostream>
#include <string>
using namespace std;

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

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