CF1969B.Shifts and Sorting

我们定义一个字符串 $s$ 的循环移位为将 $s_1 s_2 \dots s_{n-1} s_n$ 变换为 $s_n s_1 s_2 \dots s_{n-1}$。换句话说，就是把最后一个字符 $s_n$ 放到第一个字符之前，其余字符整体向右移动一位。

现在给你一个二进制字符串 $s$（只包含 $0$ 和 $1$）。

每次操作，你可以选择任意一个子串 $s_l s_{l+1} \dots s_r$（$1 \le l < r \le |s|$），对其进行一次循环移位。该操作的代价等于所选子串的长度 $r - l + 1$。

你可以进行任意次上述操作。请你求出将 $s$ 变为非递减有序（即所有 $0$ 都在 $1$ 前面）的最小总代价。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个二进制字符串 $s$（$2 \le |s| \le 2 \times 10^5$，$s_i \in \{0, 1\}$），即需要排序的字符串。

输入额外保证：所有测试用例中字符串长度之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示将字符串变为有序所需的最小总代价。

在第一个测试用例中，你可以选择整个字符串进行一次循环移位：$10 \rightarrow 01$。子串长度为 $2$，所以代价为 $2$。

在第二个测试用例中，字符串已经有序，无需操作。

在第三个测试用例中，一种最优策略如下：

1. 选择子串 $[1, 3]$：$11000 \rightarrow 01100$；
2. 选择子串 $[2, 4]$：$01100 \rightarrow 00110$；
3. 选择子串 $[3, 5]$：$00110 \rightarrow 00011$。

总代价为 $3 + 3 + 3 = 9$。

由 ChatGPT 4.1 翻译