解题思路

给定仅由 0/1 组成的字符串 s。操作允许：

• 删除任意字符（代价 1 枚硬币）
• 交换任意两个字符（免费）

我们要得到某个字符串 t，满足对所有 i ∈ [1, |t|] 都有 t_i ≠ s_i。交换免费意味着：在删除若干字符后，剩余字符的相对顺序不重要，我们只需关心剩余 0/1 的数量是否能在前 |t| 个位置与 s 的前 |t| 位逐一相反。

设：

• n = |s|
• c0 为 s 中 0 的总数，c1 为 1 的总数
• 对任意前缀长度 m (0 ≤ m ≤ n)，令 o(m) 为前 m 位中 1 的个数，z(m) = m - o(m) 为 0 的个数

为了使存在长度为 m 的漂亮字符串 t，我们需要在这 m 个位置把所有 s 中的 1 用 0 来“对冲”、把 0 用 1 来“对冲”。因此必须满足：

• 用于对冲前缀中 1 的 0 的数量：o(m) ≤ c0
• 用于对冲前缀中 0 的 1 的数量：z(m) ≤ c1

也就是说，可行的最大前缀长度 m* 是满足上述两个不等式的最大 m。此时我们只需保留恰好 o(m*) 个 0 和 z(m*) 个 1，其余全部删除。最少代价即：

答案 = n - m*

算法实现：一次线性扫描 s，维护前缀 1 的个数 ones_pref，对每个位置 i（作为前缀长度）检查

ones_pref ≤ c0  且  (i - ones_pref) ≤ c1

若成立，更新 best = i。最终输出 n - best。

该思路本质是前缀计数 + 可行性判定，利用交换“打乱顺序不影响匹配”的性质，将问题化为找“最长可对冲前缀”。

复杂度分析

• 时间复杂度：对每个测试用例线性扫描一次字符串，O(n)。总复杂度为所有用例长度之和的线性级。
• 空间复杂度：O(1) 额外空间（只需常数个计数变量）。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

def min_cost_beautiful(s):
    n = len(s)
    c0 = s.count('0')           # 0 的总数
    c1 = n - c0                 # 1 的总数
    best = 0                    # 最大可行前缀长度 m*
    ones_pref = 0               # 前缀 1 的个数

    for i, ch in enumerate(s, 1):  # i 是前缀长度
        if ch == '1':
            ones_pref += 1
        zeros_pref = i - ones_pref
        # 判断可行性：用 0 对冲前缀 1；用 1 对冲前缀 0
        if ones_pref <= c0 and zeros_pref <= c1:
            best = i

    return n - best

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1
    out_lines = []
    for _ in range(t):
        s = data[idx].strip()
        idx += 1
        out_lines.append(str(min_cost_beautiful(s)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// Main.java
// ACM 风格，类名 Main
// 思路：线性扫描前缀，检查 ones_pref <= c0 且 zeros_pref <= c1，最大可行前缀 best，答案为 n - best
import java.io.*;
import java.util.*;

public class Main {
    // 计算最小花费的函数
    static int minCostBeautiful(String s) {
        int n = s.length();
        int c0 = 0;
        for (int i = 0; i < n; i++) if (s.charAt(i) == '0') c0++;
        int c1 = n - c0;

        int best = 0;       // 最大可行前缀长度
        int onesPref = 0;   // 前缀 1 的个数

        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) == '1') onesPref++;
            int zerosPref = i - onesPref;
            // 可行性判定
            if (onesPref <= c0 && zerosPref <= c1) {
                best = i;
            }
        }
        return n - best;
    }

    public static void main(String[] args) throws Exception {
        // 根据数据范围使用 BufferedReader 提升读入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int T = Integer.parseInt(line.trim());
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            String s = br.readLine().trim();
            sb.append(minCostBeautiful(s)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 思路：线性扫描前缀，维护 ones_pref，判定 ones_pref <= c0 且 zeros_pref <= c1
// 输入输出为标准 ACM 风格
#include <bits/stdc++.h>
using namespace std;

// 计算最小花费
long long min_cost_beautiful(const string &s) {
    int n = (int)s.size();
    int c0 = 0;
    for (char ch : s) if (ch == '0') c0++;
    int c1 = n - c0;

    int best = 0;      // 最大可行前缀长度
    int ones_pref = 0; // 前缀 1 的个数

    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == '1') ones_pref++;
        int zeros_pref = i - ones_pref;
        // 可行性判断
        if (ones_pref <= c0 && zeros_pref <= c1) {
            best = i;
        }
    }
    return (long long)n - best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        string s;
        cin >> s;
        cout << min_cost_beautiful(s) << "\n";
    }
    return 0;
}

题目内容

多多在玩一个特殊的消消乐游戏。在游戏中有一个仅由 $0$ 和 $1$ 组成的字符串 $s$ ，多多只被允许做以下两种操作：

从字符串 $s$ 中删除任意一个字符。这个操作将花费 $1$ 枚硬币；

交换字符串 $s$ 中的任意两个字符。这个操作是完全免费，即不花费硬币。

现在要求多多经过上述任意多次操作，最终得到一个字将串 $t$ 。如果字符串 $t$ 满足对于从 $1$ 到 $丨t丨$( $丨t丨$ 表示字将串 $t$ 的长度)位置的字符 $t_i$ 始终有 $t_i≠s_i$ , 那么称字符串 $t$ 为一个“漂亮的字符串”(其中空字符串也被认为是一个漂亮的字符串)。

多多现在想知道最少需要花费多少枚硬币才可以得到一个漂亮的字符串。

输入描述

第一行包含一个整数 $t(1<=t<= 10^4)$,表示有 $1$ 组测试数据

每组测试数据包含一个由数字 $0$ 和 $1$ 构成的字符串 $s$ ，其中字符串 $s$ 的长度满足 $(1 <= 丨s丨<=2*10^5)$

输出描述

对于每组测试数据输出一个整数，代表最少需整花费多少枚硬币才可以得到一个“漂亮的字符串“ 。

样例1

输入

4
0
011
0101110001
111100

输出

1
1
0
4

说明

第一组测试用例中，只能删除原字符串 $0$ 得到一个空的漂亮字符串，即花费 $1$ 枚硬币；

第二组测试用例中，可以先删除最后一个字符 $1$ 得到一个字符串 $01$，然后再交换第一个和第二个字符的位置，得到一个亮字符串 $10$、总共花费 $1$ 枚硬币；

第三组测试用例中，分别交换 $1$ 和 $2$，$3$ 和 $4$ ，$5$ 和 $7$，$6$ 和 $8$，$9$ 和 $10$ 位置的字符，可以得到一个漂亮的字符串 $1010001110$ 。总共花费 $0$ 枚硬币；

第四组测试用例中，删除前 $4$ 个字符串可以得到一个漂亮的字符串 $00$ 。总共花费 $4$ 枚硬币。