A16559. Majority Wins?
编程题
普及+/提高
知识点
题目描述
给定一个长度为 $n$ 的二进制字符串 $s$。
你可以对任意长度为 $k$ 的二进制字符串 $g$ 执行如下操作一次：
- 选择一对 $l, r$，满足 $1 \leq l \leq r \leq k$；
- 将字符串 $g$ 的子串 $g_l, \ldots, g_r$ 替换为该子串中出现次数不少于另一字符的某个字符。
一次操作的代价为 $r-l+1$。
例如，字符串 010010 可以通过一次花费为 $4$ 的操作（将 1001 替换成 1）变为 010；字符串 1111 可以通过一次花费为 $4$ 的操作（对整个字符串操作）变为 1；字符串 0100 可以通过选取子串 100，将其替换成 0，例如变为 00。
你需要求出将整个字符串 $s$ 变成字符串 1 所需的最小总代价（可以进行任意次操作，也可以不进行），或者判断是否不可能实现。
注：
$^*$ 二进制字符串指仅包含 $0$ 和 $1$ 的字符串。
$^\dagger$ 子串：对于字符串 $g$，字符串 $t$ 是它的子串，当且仅当 $t$ 能从 $g$ 通过删去若干（可以为零或全部）开头和结尾的字符后得到。
你可以对任意长度为 $k$ 的二进制字符串 $g$ 执行如下操作一次：
- 选择一对 $l, r$，满足 $1 \leq l \leq r \leq k$；
- 将字符串 $g$ 的子串 $g_l, \ldots, g_r$ 替换为该子串中出现次数不少于另一字符的某个字符。
一次操作的代价为 $r-l+1$。
例如，字符串 010010 可以通过一次花费为 $4$ 的操作（将 1001 替换成 1）变为 010；字符串 1111 可以通过一次花费为 $4$ 的操作（对整个字符串操作）变为 1；字符串 0100 可以通过选取子串 100，将其替换成 0，例如变为 00。
你需要求出将整个字符串 $s$ 变成字符串 1 所需的最小总代价（可以进行任意次操作，也可以不进行），或者判断是否不可能实现。
注：
$^*$ 二进制字符串指仅包含 $0$ 和 $1$ 的字符串。
$^\dagger$ 子串：对于字符串 $g$，字符串 $t$ 是它的子串，当且仅当 $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$。
每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$），表示二进制字符串的长度。
第二行包含一个长度为 $n$ 的仅由 0 和 1 组成的字符串 $s$。
保证所有测试用例中 $n$ 之和不超过 $5 \cdot 10^5$。
输出格式
对于每个测试用例，如果无法将字符串 $s$ 变成 1，输出 $-1$。否则，输出最小总代价。
输入输出样例
输入 #1
7 1 0 1 1 2 00 2 10 3 010 8 00111000 6 100100
输出 #1
-1 0 -1 2 4 9 7
说明/提示
在第一个测试用例中，不可能得到 1，因为唯一可能的操作（$l = r = 1$）不会改变字符串。
在第二个测试用例中，初始字符串已为 1，所以答案是 0。
在第四个测试用例中，可以对整个字符串进行一次操作，将其替换为 1。此次操作的代价为 $2$。可以证明，无法获得更小的总代价。
在第二个测试用例中，初始字符串已为 1，所以答案是 0。
在第四个测试用例中，可以对整个字符串进行一次操作，将其替换为 1。此次操作的代价为 $2$。可以证明，无法获得更小的总代价。