← 返回题目列表

Codeforces · 1693/F

F. 我可能错了

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

给定一个二进制字符串 $$$S$$$,长度为 $$$n$$$,索引从 $$$1$$$ 到 $$$n$$$。您可以执行以下操作任意次数(可能为零):

- 选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$)。设 $$$cnt_0$$$ 为 $$$S[l \ldots r]$$$ 中出现 0 的次数,$$$cnt_1$$$ 为 $$$S[l \ldots r]$$$ 中出现 1 的次数。您可以支付 $$$|cnt_0 - cnt_1| + 1$$$ 硬币并对 $$$S[l \ldots r]$$$ 进行排序。 ($$$S[l \ldots r]$$$ 是指 $$$S$$$ 的子串,从位置 $$$l$$$ 开始,到位置 $$$r$$$ 结束)例如,如果 $$$S = $$$ 11001,我们可以对 $$$S[2 \ldots 4]$$$ 执行操作,支付 $$$|2 - 1| + 1 = 2$$$币,得到$$$S = $$$ 10011作为新的字符串。

求按升序对 $$$S$$$ 进行排序所需的最小硬币总数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$S$$$ 的大小。

每个测试用例的第二行包含一个二进制字符串 $$$S$$$,由 $$$n$$$ 个字符 $$$S_1S_2 \ldots S_n$$$ 组成。 (对于每个 $$$1 \le i \le n$$$,$$$S_i = $$$ 0 或 $$$S_i = $$$ 1)

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出按升序对 $$$S$$$ 进行排序所需的最小硬币总数。

示例

输入 #1

7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000

输出 #1

0
1
1
3
2
2
5

注意

在第一个测试用例中,$$$S$$$ 已经排序。

在第二个测试用例中,应用 $$$l = 1, r = 2$$$ 的操作就足够了。

在第三个测试用例中,应用 $$$l = 1, r = 2$$$ 的运算就足够了。