← 返回题目列表

AtCoder · abc408_d

G. 翻转收集

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

分数: 400 点

问题陈述

给你一个字符串 S 长度 N 组成 0 和 1.

您可以执行以下操作任意次数(可能为零):

  • 选择一个整数 i 满意 1 \leq i \leq N,并更改 S_i 来自 0 to 1,或来自 1 to 0.

您的目标是 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