分数: 400 点
问题陈述
给你一个字符串 S 长度 N 组成 0 和 1.
您可以执行以下操作任意次数(可能为零):
- 选择一个整数 i 满意 1 \leq i \leq N,并更改 S_i 来自
0to1,或来自1to0.
您的目标是 1中 S 表格 最多 1 个 间隔。找出实现目标所需的最少操作次数。
更准确地说,目标是使 S 使得存在一对整数 (l,r) 满足以下两个条件。找出实现目标所需的最少操作次数。
- 1 \leq l \leq r \leq N+1.
- S_i=
1和 l \leq i < r 对于每个整数都是等价的 i 满意 1 \leq i \leq N.
可以证明,通过有限次数的操作总能实现目标。
T 给出了测试用例,因此请解决每个测试用例。
约束
- 1 \leq T \leq 20000
- 1 \leq N \leq 2 \times 10^5
- S 是一个长度为的字符串 N 组成
0和1. - 对于每个输入文件,总和 N 所有测试用例最多 2 \times 10^5.
- T,N 是整数。
输入
输入由标准输入按以下格式给出:
T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T
\textrm{case}_i 代表 i-第一个测试用例,以以下格式给出:
N S
输出
输出 T 行。的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 5 10011 10 1111111111 7 0000000
示例输出 1
1 0 0
在第一个测试用例中,如果我们执行更改操作 S_1 to 0, 1s 将形成一个区间。另外,最初的 S 不满足条件。因此,答案是 1.
在第二个测试用例中,没有 0中 S,因此无需执行任何操作。因此,答案是 0.
在第三个测试用例中,没有 1中 S,因此无需执行任何操作。因此,答案是 0.
示例输入 2
5 2 01 10 1000010011 12 111100010011 3 111 8 00010101
示例输出 2
0 2 3 0 2