← 返回题目列表

Codeforces · 1732/B

B. 乌古

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

二进制字符串是仅由字符 0 和 1 组成的字符串。您将获得一个二进制字符串 $$$s_1 s_2 \ldots s_n$$$。需要用最少的操作次数使这个字符串不减。换句话说,每个字符不应小于前一个字符。在一项操作中,您可以执行以下操作:

- 选择字符串中的任意索引 $$$1 \leq i \leq n$$$;
- 对于所有$$$j \geq i$$$,将第$$$j$$$位置的值改为相反,即如果$$$s_j = 1$$$,则使$$$s_j = 0$$$,反之亦然。

使字符串不减最少需要多少次操作?

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行是一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 字符串的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。

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

输出

对于每个测试用例,输出一个整数 - 使字符串不递减所需的最少操作数。

示例

输入 #1

8
1
1
2
10
3
101
4
1100
5
11001
6
100010
10
0000110000
7
0101010

输出 #1

0
1
2
1
2
3
1
5

注意

在第一个测试用例中,字符串已经是非递减的。

在第二个测试用例中,您可以选择 $$$i = 1$$$,然后选择 $$$s = \mathtt{01}$$$。

在第三个测试用例中,您可以选择 $$$i = 1$$$ 并得到 $$$s = \mathtt{010}$$$,然后选择 $$$i = 2$$$。结果,我们得到 $$$s = \mathtt{001}$$$,即一个非递减的字符串。

在第六个测试用例中,您可以在第一次迭代时选择 $$$i = 5$$$ 并得到 $$$s = \mathtt{100001}$$$。然后选择 $$$i = 2$$$,然后选择 $$$s = \mathtt{111110}$$$。然后我们选择 $$$i = 1$$$,得到非递减字符串 $$$s = \mathtt{000001}$$$。