← 返回题目列表

AtCoder · abc426_d

G. 弹出并插入

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

分数: 400 点

问题陈述

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

您可以对 S 任意次数(可能为零):

  • 删除第一个或最后一个字符,翻转它(更改 0 to 1 or 1 to 0),然后将其插回任意位置。 更正式地说,让 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 从一开始就是一样的,所以不需要任何操作。