分数: 400 点
问题陈述
给你一个字符串 S 长度 N 组成 0 和 1.
您可以对 S 任意次数(可能为零):
- 删除第一个或最后一个字符,翻转它(更改
0to1or1to0),然后将其插回任意位置。 更正式地说,让 r(0)=1和 r(1)=0,并执行以下操作之一:(此处, S_i 表示 i- 第一个字符 S.)- 选择任意 i\ (1\leq i\leq N) 并更改 S to S_2\dots S_i\,r(S_1)\,S_{i+1}\dots S_N.
- 选择任意 i\ (0\leq i\leq N-1) 并更改 S to S_1\dots S_i\,r(S_N)\,S_{i+1}\dots S_{N-1}.
求使所有字符成为所需的最少操作数 S 相同。 可以证明这样的操作序列总是存在的。
你被给予 T 测试用例,因此解决每个用例。
约束
- 1\leq T\leq 2\times 10^5
- 2\leq N \leq 5\times 10^5
- T 和 N 是整数。
- S 是一个长度为的字符串 N 组成
0和1. - 总和 N 所有测试用例最多 5\times 10^5.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
\text{case}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:
N S
输出
输出 T 行。的 i第行 (1\leq i\leq T) 应包含以下问题的答案 i- 第一个测试用例。
样本输入 1
3 5 01001 3 000 15 110010111100101
示例输出 1
4 0 16
例如,对于第一个测试用例,您可以将所有字符 S 进入 0 有四个操作如下。
不可能把所有的角色都制作出来 S 与三个或更少的操作相同,所以答案是 4.
- 删除第一个字符
0,然后插入1第一个和第二个字符之间(在 删除后的 S )。 S 变为11001. - 删除第一个字符
1,然后插入0在第二个和第三个字符之间(在 S )。 S 变为10001. - 删除最后一个字符
1,然后插入0在末尾(在 S )。 S 变为10000. - 删除第一个字符
1,然后插入0开头(在 S )。 S 变为00000.
对于第二个测试用例,所有字符 S 从一开始就是一样的,所以不需要任何操作。