← 返回题目列表

Codeforces · 1969/B

B. 移位和排序

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

让我们将某个字符串 $$$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$$$ 按非降序排序的最小总成本是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含一个二进制字符串 $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$; $$$s_i \in$$$ {0, 1}) - 您需要排序的字符串。

对输入的附加约束:所有测试用例的字符串长度总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印单个整数 - 使用任意次数以上的操作对字符串进行排序的最小总成本。

示例

输入 #1

5
10
0000
11000
101011
01101001

输出 #1

2
0
9
5
11

注意

在第一个测试用例中,您可以选择整个字符串并执行循环移位:10 $$$\rightarrow$$$ 01。子字符串的长度为$$$2$$$,因此成本为$$$2$$$。

在第二个测试用例中,字符串已经排序,因此您不需要执行任何操作。

在第三个测试用例中,最佳策略之一是:

1. 选择子串 $$$[1, 3]$$$: 11000 $$$\rightarrow$$$ 01100;
2. 选择子串 $$$[2, 4]$$$: 01100 $$$\rightarrow$$$ 00110;
3. 选择子字符串 $$$[3, 5]$$$: 00110 $$$\rightarrow$$$ 00011。