A16818 | $Optimal Shifts$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个二进制字符串 $s_1s_2 \ldots s_n$，其中至少包含一个 $1$。你需要将其变为同样长度且全部由 $1$ 组成的二进制字符串。为此，你可以进行如下任意次操作： 选择一个整数 $d$（$1 \le d \le n$），将字符串 $s$ 进行循环右移 $d$ 位得到新字符串 $t$，形式化地表示为：$t = s_{n-d+1} \ldots s_{n} s_1 \ldots s_{n-d}$。之后，对所有 $j$ 满足 $t_j = 1$，执行 $s_j := 1$。该操作的花费为 $d$ 个金币。 注意，原本 $s_j=1$ 的位置即便 $t_j=0$ 也会维持为 $1$。 请你计算将 $s$ 变为全是 $1$ 的字符串所需的最小金币总数。

每组测试数据包含多组用例。第一行输入测试用例组数 $t$（$1 \le t \le 10^4$）。接下来每组测试用例如下： 每组测试用例的第一行输入整数 $n$（$1 \le n \le 2 \times 10^5$），表示二进制字符串的长度。 第二行输入一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串。 保证每个字符串至少包含一个 $1$。 保证所有用例中 $n$ 的总和不超过 $2\times10^5$。

对于每个测试用例，输出一个整数，即将所有字符变为 $1$ 所需的最小金币总数。

输入 #1

5
1
1
3
101
4
0110
11
10101010100
2
11

输出 #1

C++ 编辑器

输入

输出