CF2189E 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$ 通过删去若干（可以为零或全部）开头和结尾的字符后得到。

每组测试数据包含多组测试用例。第一行包含一个整数 $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$。

对于每个测试用例，如果无法将字符串 $s$ 变成 1，输出 $-1$。否则，输出最小总代价。

在第一个测试用例中，不可能得到 1，因为唯一可能的操作（$l = r = 1$）不会改变字符串。 在第二个测试用例中，初始字符串已为 1，所以答案是 0。 在第四个测试用例中，可以对整个字符串进行一次操作，将其替换为 1。此次操作的代价为 $2$。可以证明，无法获得更小的总代价。 由 ChatGPT 5 翻译