我想，很多人被题目误导了 如果中间有N，即打扫过的地方，就不应停止，而应继续。不然你难道扫到一半就停了 不想打注释了，自己看

题面大意 给你nnn个字符，只由大写字母NNN和OOO组成，每次可以选择kkk个连续的字符，将选中的各个字符变成NNN。 题意分析 找到最小的操作数，将所有的OOO变成NNN 解题思路 每次选择kkk个字符，如果从iii开始选，则可变的范围就是[i,i+k−1][i,i+k-1][i,i+k−1]，考虑只有OOO需要变成NNN，我们可以找到第一个为OOO的字符，从这个字符开始选择kkk个字符变成NNN,然后继续找到下一个OOO。 那么实际上每次我们只需要维护一个值rrr，它表示≤r\leq r≤r的字符都能变成NNN 时间复杂度解析 我们只需要遍历一次字符即可，复杂度为O(n)O(n)O(n) 代码演示

这道题是典型的贪心问题，关键要贪那一段含有O最多的地方，把它这个闭区间中的O都变成N

#include <iostream> #include <cstdio> using namespace std; int main(){ int n, m, ct = 0, ctt = 0; bool flag = 0; cin >> n >> m; string a; cin >> a; for(int i = 0; i < n; i++){ if(a[i] == 'O') flag = 1; if(flag) ctt++; if(ctt == m){ ctt = 0; ct++; flag = 0; } //a[i] = 'N'; }if(ctt){ ctt = 0; ct++; flag = 0; } cout << ct; }