翻译

给定一个字符串 \(s\)，你有两种操作：

1. 删除一个字符。（花费一枚金币）
2. 交换某两个字符的位置。（不花费金币）

假设经过若干次操作后得到的字符串为 \(t\)。

\(t\) 是好的当且仅当对于任意的 \(i\)（\(1 \le i \le |t|\)，\(|t|\) 为字符串 \(t\) 的长度），均满足 \(t_i \ne s_i\)。（\(s\) 是原本的字符串）

自然，空串一定是好的。

问最小花费。

多测。

思路

记录每个 \(s\) 的 0 和 1 的数量，第二次遍历时直接遍历 \(s\) 串，\(s\) 串为 1 则填 0，为 0 则填 1。当无法继续填时直接输出剩余的 0 和 1 总字符数。因为此时后面的不管怎么填一定会有相同，只能全删。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#define ll long long
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
using namespace std;
ll T;
char s[200005];
signed main()
{
    // freopen("in.in" , "r" , stdin);
    // freopen("out.out" , "w" , stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> s + 1;
        ll len = strlen(s + 1) , num0 = 0 , num1 = 0;
        fr(i , 1 , len)
        {
            if(s[i] == '0')
            {
                num0++;
            }
            else
            {
                num1++;
            }
        }
        fr(i , 1 , len)
        {
            if(s[i] == '0')
            {
                if(num1 == 0)
                {
                    break;
                }
                num1--;
            }
            else
            {
                if(num0 == 0)
                {
                    break;
                }
                num0--;
            }
        }
        cout << num1 + num0 << '\n';
    }
    return 0;
}