正经题解｜新年大扫除

题面大意

给你$n$个字符，只由大写字母$N$和$O$组成，每次可以选择$k$个连续的字符，将选中的各个字符变成$N$。

题意分析

找到最小的操作数，将所有的$O$变成$N$

解题思路

每次选择$k$个字符，如果从$i$开始选，则可变的范围就是$[i,i+k-1]$，考虑只有$O$需要变成$N$，我们可以找到第一个为$O$的字符，从这个字符开始选择$k$个字符变成$N$,然后继续找到下一个$O$。

那么实际上每次我们只需要维护一个值$r$，它表示$\leq r$的字符都能变成$N$

时间复杂度解析

我们只需要遍历一次字符即可，复杂度为$O(n)$

代码演示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,k;
    string s;
    cin >> n >> k;
    cin >> s;
    int r = -1;
    int cnt = 0;
    for(int i=0;i<s.length();i++) {
        if (s[i] == 'O' && i > r) {
            cnt ++;
            r = i + k - 1;
        }
    }
    cout << cnt << endl;
    return 0;
}