I Might Be Wrong

题意翻译

### 题目描述 给定一个长度为 $n$ 的 `01` 字符串 $S$。 你可以进行下列操作任意次： - 选择 $S$ 的一个连续子串 $S[l,r]$。 设 $cnt_0,cnt_1$ 分别表示该子段中字符 `0` 和字符 `1` 的数量。 则你将花费 $|cnt_0-cnt_1|+1$ 枚金币并对 $S[l,r]$ 进行升序排序。 你需要求出使 $S$ 本身升序排序所需的最少金币数。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^3)$ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $n(1\leq n,\sum n\leq2\times10^5)$。 接下来一行输入 $n$ 个字符表示 `01` 字符串 $S$。 ### 输出格式 对于每组数据： 输出对 $S$ 排序所需的最少金币数。 ### 样例解释 对于第三组数据： - 我们可以选择子串 $S[1,2]$，此时 $cnt_0=cnt_1=1$，因此花费 $|1-1|+1$，即 $1$ 枚金币。 操作后 $S=\texttt{"011"}$，满足要求，共计花费 $1$ 枚金币。 对于第六组数据： - 第一次操作选择子串 $S[1,4]$，此时 $cnt_0=cnt_1=2$，因此花费 $|2-2|+1$，即 $1$ 枚金币。 操作后 $S=\texttt{"001100"}$。 - 第二次操作选择子串 $S[3,6]$，此时 $cnt_0=cnt_1=2$，因此花费 $|2-2|+1$，即 $1$ 枚金币。 操作后 $S=\texttt{"000011"}$，满足要求，共计花费 $2$ 枚金币。

题目描述

You are given a binary string $ S $ of length $ n $ indexed from $ 1 $ to $ n $ . You can perform the following operation any number of times (possibly zero): - Choose two integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ). Let $ cnt_0 $ be the number of times 0 occurs in $ S[l \ldots r] $ and $ cnt_1 $ be the number of times 1 occurs in $ S[l \ldots r] $ . You can pay $ |cnt_0 - cnt_1| + 1 $ coins and sort the $ S[l \ldots r] $ . (by $ S[l \ldots r] $ we mean the substring of $ S $ starting at position $ l $ and ending at position $ r $ ) For example if $ S = $ 11001, we can perform the operation on $ S[2 \ldots 4] $ , paying $ |2 - 1| + 1 = 2 $ coins, and obtain $ S = $ 10011 as a new string. Find the minimum total number of coins required to sort $ S $ in increasing order.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of $ S $ . The second line of each test case contains a binary string $ S $ of $ n $ characters $ S_1S_2 \ldots S_n $ . ( $ S_i = $ 0 or $ S_i = $ 1 for each $ 1 \le i \le n $ ) It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output the minimum total number of coins required to sort $ S $ in increasing order.

输入输出样例

输入样例 #1

7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000

输出样例 #1

0
1
1
3
2
2
5

说明

In the first test case, $ S $ is already sorted. In the second test case, it's enough to apply the operation with $ l = 1, r = 2 $ . In the third test case, it's enough to apply the operation with $ l = 1, r = 2 $ .

**题意翻译**

题目描述：
给定一个长度为 $ n $ 的 `01` 字符串 $ S $。
你可以进行以下操作任意次：

- 选择 $ S $ 的一个连续子串 $ S[l,r] $。
设 $ cnt_0, cnt_1 $ 分别表示该子段中字符 `0` 和字符 `1` 的数量。
则你将花费 $ |cnt_0-cnt_1|+1 $ 枚金币并对 $ S[l,r] $ 进行升序排序。

你需要求出使 $ S $ 本身升序排序所需的最少金币数。

输入格式：
第一行输入一个整数 $ t(1\leq t\leq10^3) $ 表示数据组数，接下来对于每组数据：
第一行输入一个整数 $ n(1\leq n,\sum n\leq2\times10^5) $。
接下来一行输入 $ n $ 个字符表示 `01` 字符串 $ S $。

输出格式：
对于每组数据：
输出对 $ S $ 排序所需的最少金币数。

样例解释：
对于第三组数据：

- 我们可以选择子串 $ S[1,2] $，此时 $ cnt_0=cnt_1=1 $，因此花费 $ |1-1|+1 $，即 $ 1 $ 枚金币。
操作后 $ S=\texttt{"011"} $，满足要求，共计花费 $ 1 $ 枚金币。

对于第六组数据：

- 第一次操作选择子串 $ S[1,4] $，此时 $ cnt_0=cnt_1=2 $，因此花费 $ |2-2|+1 $，即 $ 1 $ 枚金币。
操作后 $ S=\texttt{"001100"} $。
- 第二次操作选择子串 $ S[3,6] $，此时 $ cnt_0=cnt_1=2 $，因此花费 $ |2-2|+1 $，即 $ 1 $ 枚金币。
操作后 $ S=\texttt{"000011"} $，满足要求，共计花费 $ 2 $ 枚金币。

**题目描述**

给定一个长度为 $ n $ 的二进制字符串 $ S $，索引从 $ 1 $ 到 $ n $。你可以进行任意次数的以下操作（可能为零次）：

- 选择两个整数 $ l $ 和 $ r $（$ 1 \le l \le r \le n $）。设 $ cnt_0 $ 为 $ S[l \ldots r] $ 中 `0` 的数量，$ cnt_1 $ 为 `1` 的数量。你可以支付 $ |cnt_0 - cnt_1| + 1 $ 枚金币并对 $ S[l \ldots r] $ 进行升序排序。

例如，如果 $ S = $ 11001，我们可以对 $ S[2 \ldots 4] $ 进行操作，支付 $ |2 - 1| + 1 = 2 $ 枚金币，得到 $ S = $ 10011 作为新字符串。

找出将 $ S $ 排序成升序所需的最少金币总数。

**输入输出格式**

输入格式：
第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 2 \times 10^5 $）——$ S $ 的大小。

每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ S $，由字符 $ S_1S_2 \ldots S_n $ 组成。（对于每个 $ 1 \le i \le n $，$ S_i = $ 0 或 $ S_i = $ 1）

保证所有测试用例的 $ n $ 之和不超过 $ 2 \times 10^5 $。

输出格式：
对于每个测试用例，输出将 $ S $ 排序成升序所需的最少金币总数。

**输入输出样例**

输入样例 #1：
```
7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000
```

输出样例 #1：
```
0
1
1
3
2
2
5
```**题意翻译** 题目描述： 给定一个长度为 $ n $ 的 `01` 字符串 $ S $。 你可以进行以下操作任意次： - 选择 $ S $ 的一个连续子串 $ S[l,r] $。 设 $ cnt_0, cnt_1 $ 分别表示该子段中字符 `0` 和字符 `1` 的数量。 则你将花费 $ |cnt_0-cnt_1|+1 $ 枚金币并对 $ S[l,r] $ 进行升序排序。 你需要求出使 $ S $ 本身升序排序所需的最少金币数。 输入格式： 第一行输入一个整数 $ t(1\leq t\leq10^3) $ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $ n(1\leq n,\sum n\leq2\times10^5) $。 接下来一行输入 $ n $ 个字符表示 `01` 字符串 $ S $。 输出格式： 对于每组数据： 输出对 $ S $ 排序所需的最少金币数。 样例解释： 对于第三组数据： - 我们可以选择子串 $ S[1,2] $，此时 $ cnt_0=cnt_1=1 $，因此花费 $ |1-1|+1 $，即 $ 1 $ 枚金币。 操作后 $ S=\texttt{"011"} $，满足要求，共计花费 $ 1 $ 枚金币。 对于第六组数据： - 第一次操作选择子串 $ S[1,4] $，此时 $ cnt_0=cnt_1=2 $，因此花费 $ |2-2|+1 $，即 $ 1 $ 枚金币。 操作后 $ S=\texttt{"001100"} $。 - 第二次操作选择子串 $ S[3,6] $，此时 $ cnt_0=cnt_1=2 $，因此花费 $ |2-2|+1 $，即 $ 1 $ 枚金币。 操作后 $ S=\texttt{"000011"} $，满足要求，共计花费 $ 2 $ 枚金币。 **题目描述** 给定一个长度为 $ n $ 的二进制字符串 $ S $，索引从 $ 1 $ 到 $ n $。你可以进行任意次数的以下操作（可能为零次）： - 选择两个整数 $ l $ 和 $ r $（$ 1 \le l \le r \le n $）。设 $ cnt_0 $ 为 $ S[l \ldots r] $ 中 `0` 的数量，$ cnt_1 $ 为 `1` 的数量。你可以支付 $ |cnt_0 - cnt_1| + 1 $ 枚金币并对 $ S[l \ldots r] $ 进行升序排序。 例如，如果 $ S = $ 11001，我们可以对 $ S[2 \ldots 4] $ 进行操作，支付 $ |2 - 1| + 1 = 2 $ 枚金币，得到 $ S = $ 10011 作为新字符串。 找出将 $ S $ 排序成升序所需的最少金币总数。 **输入输出格式** 输入格式： 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 2 \times 10^5 $）——$ S $ 的大小。 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ S $，由字符 $ S_1S_2 \ldots S_n $ 组成。（对于每个 $ 1 \le i \le n $，$ S_i = $ 0 或 $ S_i = $ 1） 保证所有测试用例的 $ n $ 之和不超过 $ 2 \times 10^5 $。 输出格式： 对于每个测试用例，输出将 $ S $ 排序成升序所需的最少金币总数。 **输入输出样例** 输入样例 #1： ``` 7 1 1 2 10 3 101 4 1000 5 11010 6 110000 20 01000010001010011000 ``` 输出样例 #1： ``` 0 1 1 3 2 2 5 ```