CF1809D Binary String Sorting

给定一个只包含字符 $0$ 和 $1$ 的二进制字符串 $s$。 你可以对该字符串进行若干次（也可以不进行）如下两种操作： - 选择两个相邻的元素并交换它们。执行该操作需要支付 $10^{12}$ 个硬币； - 选择字符串中的任意一个元素并将其删除。执行该操作需要支付 $10^{12}+1$ 个硬币。 你的任务是计算将字符串 $s$ 排序为非递减序列（即使得 $s_1 \le s_2 \le \dots \le s_m$，其中 $m$ 为所有操作后字符串的长度）所需支付的最少硬币数。空字符串也被认为是非递减序列。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例仅一行，包含一个只由字符 $0$ 和 $1$ 组成的字符串 $s$（$1 \le |s| \le 3 \times 10^5$）。 所有字符串长度之和不超过 $3 \times 10^5$。

对于每个测试用例，输出一个整数，表示将字符串 $s$ 排序为非递减序列所需支付的最少硬币数。

在第一个样例中，你需要删除第 $1$ 个元素，使字符串变为 $00$。 在第二个样例中，字符串已经是有序的。 在第三个样例中，你需要交换第 $2$ 个和第 $3$ 个元素，使字符串变为 $0011$。 在第四个样例中，你需要先交换第 $3$ 个和第 $4$ 个元素，使字符串变为 $00011101$，然后删除第 $7$ 个元素，使字符串变为 $0001111$。 在第五个样例中，你需要删除第 $1$ 个元素，使字符串变为 $001101$，然后删除第 $5$ 个元素，使字符串变为 $00111$。 在第六个样例中，字符串已经是有序的。 由 ChatGPT 4.1 翻译