← 返回题目列表

Codeforces · 1913/B

B. 交换和删除

中文机器翻译题面 查看原题

给定一个二进制字符串 $$$s$$$ (仅由 0 和 1 组成的字符串)。

您可以对$$$s$$$执行两种类型的操作:

1. 从$$$s$$$中删除一个字符。此操作需要花费$$$1$$$硬币;
2. 交换$$$s$$$中的任意一对字符。此操作是免费的(花费 $$$0$$$ 硬币)。

您可以按任意顺序执行这些操作任意次数。

让我们将执行上述操作后得到的字符串命名为$$$t$$$。如果对于从 $$$1$$$ 到 $$$|t|$$$ $$$t_i \neq s_i$$$ 的每个 $$$i$$$ 字符串 $$$t$$$ 是好的($$$|t|$$$ 是字符串 $$$t$$$ 的长度)。空字符串总是好的。请注意,您正在将结果字符串 $$$t$$$ 与初始字符串 $$$s$$$ 进行比较。

使字符串 $$$t$$$ 变得良好的最小总成本是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的唯一行包含一个二进制字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$; $$$s_i \in \{$$$0, 1$$$\}$$$) - 初始字符串,由字符 0 和/或 1 组成。

对输入的附加限制:所有字符串 $$$s$$$ 的总长度不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 使字符串 $$$t$$$ 良好的最小总成本。

示例

输入 #1

4
0
011
0101110001
111100

输出 #1

1
1
0
4

注意

在第一个测试用例中,您必须从 $$$s$$$ 中删除一个字符才能得到空字符串 $$$t$$$。只有这样$$$t$$$ 才变得好。删除一次需要花费 $$$1$$$ 硬币。

在第二个测试用例中,例如,您可以从 $$$s$$$ 中删除第二个字符以获取字符串 01,然后交换第一个和第二个字符以获取字符串 $$$t$$$ $$$=$$$ 10. 字符串 $$$t$$$ 很好,因为 $$$t_1 \neq s_1$$$ 和 $$$t_2 \neq s_2$$$。总成本为 $$$1$$$ 硬币。

在第三个测试用例中,例如,您可以将 $$$s_1$$$ 与 $$$s_2$$$ 交换、$$$s_3$$$ 与 $$$s_4$$$ 交换、$$$s_5$$$ 与 $$$s_7$$$ 交换、$$$s_6$$$ 与 $$$s_8$$$ 交换、$$$s_9$$$ 与 $$$s_9$$$ 交换。 $$$s_{10}$$$。您将获得 $$$t$$$ $$$=$$$ 1010001110。所有交换操作都是免费的,因此总成本为 $$$0$$$。