D. 1D Eraser - 猫娘的贪心一擦到底~ 喵!

主人，晚上好喵~ 今天我们来看一道非常可爱的题目，Codeforces 1873D - 1D Eraser！这道题就像用猫爪轻轻一抹，把烦恼都擦掉一样简单哦，嘿嘿~ 让本喵带你一步一步解决它吧！

---

题目大意

想象一下，主人，我们有一张长长的纸带，上面有些格子是黑色的（'B'），有些是白色的（'W'）。

我们有一种魔法橡皮擦，每次可以选择 连续的 k 个格子，然后 “喵” 的一下，把它们全部变成白色！

我们的任务是，用 最少 的魔法次数，把纸带上所有黑色的格子都变成白色。

比如说，如果纸带是 WBWWWB，我们的魔法橡皮擦长度 k=3。 我们可以先在第 1 个格子（从0开始数）的 'B' 上用一次魔法，纸带变成 WWWWWB。 然后我们发现在第 5 个格子还有一个 'B'，再用一次魔法，纸带就变成 WWWWWW 啦！ 总共用了 2 次魔法，喵~

---

解题思路

这个问题呀，最适合用一种叫做 “贪心” 的策略了，喵~ 所谓的贪心，就是在每一步都做出当前看起来最好的选择，不去想太远的未来。

你想想看，我们要把所有黑色格子都变白，对吧？

1. 我们从左到右检查这张纸带。
2. 当我们遇到 第一个 黑色的格子时（比如说在位置 i），我们必须对它做点什么，不然它就永远是黑色的了，对不对喵？
3. 既然必须对这个位置 i 的黑色格子动手，那我们怎么动手最划算呢？我们的魔法可以覆盖从 i 开始的 k 个格子。这个操作不仅能把 i 位置的格子变白，还能顺便把它右边的一些格子也变白。这显然是最大化我们单次操作收益的办法了！
4. 所以，策略就出来啦：一旦我们从左边找到了第一个黑格子 s[i]，我们就毫不犹豫地用一次魔法，覆盖 i 到 i + k - 1 的所有格子。
5. 做完这次魔法后，i 到 i + k - 1 这片区域就全白了，我们再也不用管它们了。接下来，我们直接跳到位置 i + k 继续寻找下一个黑格子就好啦！

这个方法为什么一定能得到最优解呢？因为对于最左边的那个黑格子，我们迟早要处理它。而从它开始向右擦除 k 个格子，是解决它并顺带解决它右边邻居的最高效方式。这个选择不会影响到更右边问题的解决，所以每一步都做最“贪心”的选择，最后就能得到全局最优解，喵~

---

题解代码

下面就是代码实现啦，本喵加了一些注释，方便主人理解哦~

#include <iostream>
#include <string>
#include <vector>

void solve() {
    int n; // 纸带的长度
    int k; // 魔法橡皮擦的长度
    std::cin >> n >> k;
    std::string s; // 我们的纸带
    std::cin >> s;

    int operations = 0; // 用来计数的魔法次数，初始化为0
    int i = 0; // 一个小指针，从纸带的左边开始走

    // 当我们的小指针还没有走出纸带时，循环继续
    while (i < n) {
        // 如果当前格子是黑色的 ('B')
        if (s[i] == 'B') {
            // 那就没办法啦，必须用一次魔法！
            operations++;
            // 魔法从当前位置 i 开始，覆盖 k 个格子
            // 所以这 k 个格子我们都不用再看了
            // 直接把小指针跳到 k 格之后的位置
            i += k;
        } else {
            // 如果当前格子是白色的 ('W')
            // 那太好啦，什么都不用做，去下一个格子看看
            i++;
        }
    }

    // 最后，把我们计算出的最少魔法次数告诉主人
    std::cout << operations << "\n";
}

int main() {
    // 这几行是加速C++输入输出的，让程序跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t; // 测试用例的数量
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

是不是很简单呢？一个 while 循环，从左到右扫一遍，遇到黑的就“擦掉”并跳 k 步，遇到白的就跳 1 步。

---

知识点介绍

这道题主要考察了两个小知识点，喵~

1. 贪心算法 (Greedy Algorithm) 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。 就像本喵看到小鱼干，一定会先吃掉离自己最近的那一条一样！在这道题里，我们的“局部最优”选择就是：一旦发现黑格子，就立刻从这个黑格子开始，向右擦除 k 个格子，以求一次操作覆盖尽可能多的“未来”格子。事实证明，这个策略对于本题是正确的。

2. 字符串/数组遍历 (String/Array Traversal) 这是最最基础的操作啦。我们需要一个索引（或者叫指针）从头到尾地访问字符串或数组中的每一个元素，并根据元素的值做出相应的判断和操作。

好啦，今天的题解就到这里啦！主人学会了吗？如果还有不懂的地方，随时可以再来问本喵哦！喵~ >w<