← 返回题目列表

Codeforces · 2189/E

E. 多数获胜?

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

给你一个二进制字符串$$$^{\text{*}}$$$ $$$s$$$,长度为$$$n$$$。

在一个长度为 $$$k$$$ 的二进制字符串 $$$g$$$ 的操作中,您可以执行以下操作:

  • 选择一些 $$$l, r$$$ 使得 $$$1 \leq l \leq r \leq k$$$;

  • 将字符串 $$$g$$$ 的子字符串 $$$^{\text{†}}$$$ $$$g_l, \ldots, g_r$$$ 替换为 一 字符在此子字符串中出现的次数至少与其他字符相同。

此类操作的成本将等于 $$$r-l+1$$$。

例如,字符串 010010 可以转化为 010 在一次操作中替换子字符串,成本为 $$$4$$$ 1001 与 1;字符串 1111 可以转化为 1 通过对整个字符串执行成本为 $$$4$$$ 的操作,并且该字符串 例如, 0100 可以转换为 00 通过获取子字符串 100.

你需要找到将整个字符串 $$$s$$$ 转换为字符串的最小成本 1,使用多个(可能没有)操作,或确定这是不可能的。

$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$0$$$ 和 $$$1$$$ 组成的字符串。

$$$^{\text{†}}$$$ 字符串 $$$t$$$ 是字符串 $$$g$$$ 的子字符串,如果 $$$t$$$ 可以通过从 $$$g$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

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

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

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串,由字符组成 0 和 1 — 字符串 $$$s$$$。

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

输出

对于每个测试用例,如果无法获取字符串 1,输出$$$-1$$$。否则,输出最小成本。

示例

输入
复制

7
1
0
1
1
2
00
2
10
3
010
8
00111000
6
100100

输出
复制

-1
0
-1
2
4
9
7

注意

在第一个测试用例中,无法获得 1,因为唯一可能的操作 ($$$l = r = 1$$$) 不会更改字符串。

在第二个测试用例中,字符串已经是 1 最初,所以答案是 0.

在第四个测试用例中,可以对整个字符串执行操作,将其替换为 1。此操作的成本为 $$$2$$$。可见无法获取字符串 1 成本更低。