310953: CF1913B. Swap and Delete
Description
You are given a binary string $s$ (a string consisting only of 0-s and 1-s).
You can perform two types of operations on $s$:
- delete one character from $s$. This operation costs $1$ coin;
- swap any pair of characters in $s$. This operation is free (costs $0$ coins).
You can perform these operations any number of times and in any order.
Let's name a string you've got after performing operations above as $t$. The string $t$ is good if for each $i$ from $1$ to $|t|$ $t_i \neq s_i$ ($|t|$ is the length of the string $t$). The empty string is always good. Note that you are comparing the resulting string $t$ with the initial string $s$.
What is the minimum total cost to make the string $t$ good?
InputThe first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.
The only line of each test case contains a binary string $s$ ($1 \le |s| \le 2 \cdot 10^5$; $s_i \in \{$0, 1$\}$) — the initial string, consisting of characters 0 and/or 1.
Additional constraint on the input: the total length of all strings $s$ doesn't exceed $2 \cdot 10^5$.
OutputFor each test case, print one integer — the minimum total cost to make string $t$ good.
ExampleInput4 0 011 0101110001 111100Output
1 1 0 4Note
In the first test case, you have to delete a character from $s$ to get the empty string $t$. Only then $t$ becomes good. One deletion costs $1$ coin.
In the second test case, you can, for example, delete the second character from $s$ to get the string 01, and then swap the first and second characters to get the string $t$ $=$ 10. String $t$ is good, since $t_1 \neq s_1$ and $t_2 \neq s_2$. The total cost is $1$ coin.
In the third test case, you can, for example, swap $s_1$ with $s_2$, swap $s_3$ with $s_4$, swap $s_5$ with $s_7$, $s_6$ with $s_8$ and $s_9$ with $s_{10}$. You'll get $t$ $=$ 1010001110. All swap operations are free, so the total cost is $0$.
Output
题目名为“交换与删除”（Swap and Delete）。给定一个由0和1组成的二进制字符串s。你可以对s执行两种操作：
1. 删除s中的一个字符，这个操作需要花费1枚硬币。
2. 交换s中的任意两个字符，这个操作是免费的，不花费硬币。
可以任意次数和顺序执行这些操作。将执行操作后得到的字符串命名为t。如果对于每个i（从1到t的长度），t_i 不等于 s_i，则称字符串t是好的。空字符串总是好的。注意，你要将得到的字符串t与初始字符串s进行比较。
问题是：使字符串t变得好的最小总花费是多少？
输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 接下来的每行包含一个二进制字符串s（1 ≤ |s| ≤ 2 × 10^5；s_i ∈ {0, 1}），表示一个测试用例的初始字符串，由字符0和/或1组成。
- 输入的附加限制：所有字符串s的总长度不超过2 × 10^5。
输出：
- 对于每个测试用例，输出一个整数，表示使字符串t变得好的最小总花费。
示例输入输出：
输入：
```
4
0
011
0101110001
111100
```
输出：
```
1
1
0
4
```
注意：
- 在第一个测试用例中，你必须删除s中的一个字符以得到空字符串t，这样t才是好的。一次删除花费1枚硬币。
- 在第二个测试用例中，例如，你可以删除s中的第二个字符得到字符串01，然后交换前两个字符得到字符串t = 10。字符串t是好的，因为t_1 ≠ s_1且t_2 ≠ s_2。总花费是1枚硬币。
- 在第三个测试用例中，例如，你可以交换s_1和s_2，s_3和s_4，s_5和s_7，s_6和s_8，以及s_9和s_10。你会得到t = 1010001110。所有交换操作都是免费的，所以总花费是0。题目大意： 题目名为“交换与删除”（Swap and Delete）。给定一个由0和1组成的二进制字符串s。你可以对s执行两种操作： 1. 删除s中的一个字符，这个操作需要花费1枚硬币。 2. 交换s中的任意两个字符，这个操作是免费的，不花费硬币。 可以任意次数和顺序执行这些操作。将执行操作后得到的字符串命名为t。如果对于每个i（从1到t的长度），t_i 不等于 s_i，则称字符串t是好的。空字符串总是好的。注意，你要将得到的字符串t与初始字符串s进行比较。 问题是：使字符串t变得好的最小总花费是多少？ 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 接下来的每行包含一个二进制字符串s（1 ≤ |s| ≤ 2 × 10^5；s_i ∈ {0, 1}），表示一个测试用例的初始字符串，由字符0和/或1组成。 - 输入的附加限制：所有字符串s的总长度不超过2 × 10^5。 输出： - 对于每个测试用例，输出一个整数，表示使字符串t变得好的最小总花费。 示例输入输出： 输入： ``` 4 0 011 0101110001 111100 ``` 输出： ``` 1 1 0 4 ``` 注意： - 在第一个测试用例中，你必须删除s中的一个字符以得到空字符串t，这样t才是好的。一次删除花费1枚硬币。 - 在第二个测试用例中，例如，你可以删除s中的第二个字符得到字符串01，然后交换前两个字符得到字符串t = 10。字符串t是好的，因为t_1 ≠ s_1且t_2 ≠ s_2。总花费是1枚硬币。 - 在第三个测试用例中，例如，你可以交换s_1和s_2，s_3和s_4，s_5和s_7，s_6和s_8，以及s_9和s_10。你会得到t = 1010001110。所有交换操作都是免费的，所以总花费是0。