喵~ 各位算法大师们，大家好呀！我是你们的好朋友喵喵酱。今天我们要一起解决一个关于字符串的有趣问题，它看起来有点绕，但只要我们理清思路，就会发现它其实是一只温顺的小猫咪呢，喵~

Problem: 1913B - Swap and Delete

让我们先来一起看看这道题目的要求吧！

题目大意

我们有一个只包含 '0' 和 '1' 的二进制字符串 s。

我们可以对这个字符串 s 进行两种操作：

1. 删除 一个字符，这个操作需要花费 1 个金币。呜...好贵...
2. 交换 字符串中任意两个字符的位置，这个操作是 免费 的！太棒了喵！

我们可以按任意顺序、任意次数地执行这些操作。经过一系列操作后，我们会得到一个新的字符串，我们叫它 t。

这个新的字符串 t 如果要被称为一个 “好” 字符串，它必须满足一个条件：对于 t 中的每一个位置 i，t 在这个位置的字符 t[i] 必须和 原始字符串 s 在相应位置的字符 s[i] 不相同。也就是说 t[i] ≠ s[i]。

注意哦，空字符串也总是一个“好”字符串。

那么问题来了：要得到一个“好”字符串 t，我们最少需要花费多少金币呢？

---

解题思路

既然交换操作是免费的，那我们肯定想要尽可能地利用它，对不对呀？金币要花在刀刃上，所以我们应该尽可能少地执行删除操作。

这道题的目标是最小化花费，也就等价于最小化删除的字符数量。反过来想，就是要最大化保留的字符数量！

让我们想一想，一个字符能被保留下来的条件是什么？

假设我们决定保留原始字符串 s 中的一部分字符，并将它们重新排列组成新的字符串 t。对于 t 中的每一个位置 i，它都对应着 s 中的一个原始位置。

• 如果 s[i] 是 '0'，为了满足 t[i] ≠ s[i]，那么 t[i] 必须是 '1'。
• 如果 s[i] 是 '1'，为了满足 t[i] ≠ s[i]，那么 t[i] 必须是 '0'。

这意味着，对于我们保留下来的每一个原始位置，我们都需要一个与它原始字符相反的字符来填充。这些用来填充的字符也必须来自我们保留下来的字符中。

这就启发了我们一个非常直接的贪心思路，喵~

1. 清点资源：我们先把原始字符串 s 中所有 '0' 和 '1' 的数量数出来。这就像是我们的“素材库”，里面有若干个 '0' 和 '1' 可以用来交换。

2. 贪心匹配：我们从左到右遍历原始字符串 s。对于每一个位置 i：

   • 如果 s[i] 是 '0'，我们就需要找一个 '1' 来和它配对（将来可以把这个 '1' 换到 i 位置上）。我们看看“素材库”里还有没有 '1' 可用。如果有，太好了！我们成功地为这个位置找到了一个“归宿”，于是从素材库里消耗掉一个 '1'。这个位置的字符保住了！
   • 如果 s[i] 是 '1'，同理，我们看看“素材库”里还有没有 '0' 可用。如果有，就消耗一个 '0'。
   • 万一...没有了呢？ 比如说，当前 s[i] 是 '0'，但我们的“素材库”里一个 '1' 都没有了。这意味着我们剩下的所有可用字符全都是 '0'，我们再也找不到 '1' 来满足 t[i] ≠ s[i] 的条件了。

3. 计算结果：一旦我们在某个位置匹配失败了，就说明从这个位置开始，以及它后面的所有字符，都无法再被成功配对了。它们只能被可怜地删除掉，呜呜~ 此时，我们就可以停下遍历了。

最后，那些在“素材库”里被我们消耗掉的字符，就是可以成功配对并保留下来的。而“素材库”里剩下的字符，就是那些找不到配对，最终必须被删除的字符。它们的总数，就是我们的最小花费！

举个例子：s = 111100

• 素材库：4 个 '1'，2 个 '0'。
• 遍历 s[0] = '1'：需要一个 '0'。素材库里有，用掉一个。素材库剩：4 个 '1'，1 个 '0'。
• 遍历 s[1] = '1'：需要一个 '0'。素材库里还有，用掉一个。素材库剩：4 个 '1'，0 个 '0'。
• 遍历 s[2] = '1'：需要一个 '0'。可是...素材库里已经没有 '0' 了！匹配失败！
• 停下来。此时素材库里还剩下 4 个 '1' 和 0 个 '0'。总共 4 + 0 = 4 个字符。所以，最小花费就是 4。

是不是很简单呀，喵~

---

题解代码

下面就是根据这个思路写出的 C++ 代码啦！

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    std::string s;
    std::cin >> s;

    // 步骤1：清点我们的“素材库”
    int count0 = 0;
    int count1 = 0;
    for (char c : s) {
        if (c == '0') {
            count0++;
        } else {
            count1++;
        }
    }

    // 步骤2：贪心匹配
    for (char c : s) {
        if (c == '0') {
            // 当前是 '0'，需要一个 '1' 来配对
            if (count1 > 0) {
                count1--; // 消耗一个 '1'
            } else {
                // 没有 '1' 了，匹配失败，停下
                break;
            }
        } else { // c == '1'
            // 当前是 '1'，需要一个 '0' 来配对
            if (count0 > 0) {
                count0--; // 消耗一个 '0'
            } else {
                // 没有 '0' 了，匹配失败，停下
                break;
            }
        }
    }

    // 步骤3：计算结果
    // 循环结束后，count0 和 count1 里剩下的就是必须删除的字符数量
    std::cout << count0 + count1 << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码讲解

• int count0 = 0; int count1 = 0; ...：这里我们创建了两个变量 count0 和 count1，用来存放字符串 s 中 '0' 和 '1' 的总数。这就是我们的“素材库”。
• for (char c : s) { ... }：这个循环从头到尾遍历字符串 s，实现我们的贪心匹配过程。
• if (c == '0') { if (count1 > 0) ... }：如果当前字符是 '0'，我们就检查 count1 是否大于0。如果是，说明我们有 '1' 可以用来配对，于是就将 count1 减一。如果不是，说明没有 '1' 了，配对失败，执行 break 跳出循环。
• else { if (count0 > 0) ... }：对当前字符是 '1' 的情况做同样的处理。
• std::cout << count0 + count1 << "\n";：当循环结束时（无论是正常遍历完还是中途 break），count0 和 count1 中剩下的就是无法配对的字符数量。它们的和就是必须删除的字符数，也就是最小花费。

---

相关知识点

贪心算法 (Greedy Algorithm)

贪心算法就像一只看到小鱼干就马上扑过去的小猫，喵~ 它在解决问题的每一步中，都采取在当前状态下看起来最好或最优的选择，并希望这样一系列的局部最优选择能够最终导向全局最优解。

在这道题里，我们的“贪心”体现在：对于每一个位置，只要有可能通过交换来保住它（即有相反的字符可用），我们就立刻这么做。因为保住一个字符（花费0）永远比删除它（花费1）要划算。这个局部最优的选择最终导向了全局最优解（删除最少的字符）。

贪心算法并不总是能得到全局最优解，但对于这道题和许多其他特定结构的问题，它被证明是正确且高效的。

字符串处理

这道题也考察了基本的字符串操作，比如遍历和计数。在 C++ 中，使用范围 for 循环 (for (char c : s)) 是遍历字符串或容器中每个元素的非常简洁和现代的方式，推荐大家多多使用哦！

好啦，这道题的讲解就到这里啦！是不是感觉思路清晰了很多呢？希望大家都能明白，并且享受算法的乐趣喵~ 下次再见啦！