CF1732B Ugu

一个二进制字符串是只包含字符 $0$ 和 $1$ 的字符串。给定一个二进制字符串 $s_1 s_2 \ldots s_n$，你需要通过最少的操作次数使该字符串变为非递减的。换句话说，每个字符都不小于前一个字符。 每次操作，你可以进行如下操作： - 选择字符串中的任意一个下标 $1 \leq i \leq n$； - 对所有 $j \geq i$ 的位置，将第 $j$ 个字符取反，即如果 $s_j = 1$，则变为 $0$，如果 $s_j = 0$，则变为 $1$。 请问，最少需要多少次操作才能使字符串变为非递减的？

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据组数。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示字符串的长度。 每组测试数据的第二行包含一个长度为 $n$ 的二进制字符串 $s$。 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出一个整数，表示将字符串变为非递减所需的最少操作次数。

在第一个测试用例中，字符串已经是非递减的。 在第二个测试用例中，可以选择 $i = 1$，此时 $s = \mathtt{01}$。 在第三个测试用例中，可以选择 $i = 1$，得到 $s = \mathtt{010}$，然后选择 $i = 2$，最终得到 $s = \mathtt{001}$，即非递减字符串。 在第六个测试用例中，第一次选择 $i = 5$，得到 $s = \mathtt{100001}$。然后选择 $i = 2$，此时 $s = \mathtt{111110}$。最后选择 $i = 1$，得到非递减字符串 $s = \mathtt{000001}$。 由 ChatGPT 4.1 翻译