Binary String

题意翻译

### 题目描述 你有一个由 $1$ 和 $0$ 构成的字符串 $s$。 你需要先从 $s$ 的开头移除若干字符，然后从 $s$ 的结尾移除若干字符。（当然，你可以不移除任何字符，也可以将整个 $s$ 移除掉） 这样做的代价是从 $s$ 中移除的 $1$ 的个数和 $s$ 中剩余的 $0$ 的个数的最大值。 求代价的最小值。 ### 输入格式 第一行一个整数 $t$ 表示数据组数。$(1\le t\le 10^4)$ 接下来 $t$ 行，每行一个字符串 $s$ 表示这组数据的 $s$。$(1\le |s|\le 2⋅10^5)$ $s$ 的总和不超过 $2⋅10^5$。 ### 输出格式 对于每组数据，输出一个整数表示最小代价。 ### 说明/提示 样例解释： `101110110` -> `(10) 111011 (0)` `1001001001001` -> `(100100) 1001 (001)` `0000111111` -> `(0000) 111111 ()` `00000` -> `(00000)()` `1111` -> `()1111()`

题目描述

You are given a string $ s $ consisting of characters 0 and/or 1. You have to remove several (possibly zero) characters from the beginning of the string, and then several (possibly zero) characters from the end of the string. The string may become empty after the removals. The cost of the removal is the maximum of the following two values: - the number of characters 0 left in the string; - the number of characters 1 removed from the string. What is the minimum cost of removal you can achieve?

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of one line containing the string $ s $ ( $ 1 \le |s| \le 2 \cdot 10^5 $ ), consisting of characters 0 and/or 1. The total length of strings $ s $ in all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print one integer — the minimum cost of removal you can achieve.

输入输出样例

输入样例 #1

5
101110110
1001001001001
0000111111
00000
1111

输出样例 #1

1
3
0
0
0

说明

Consider the test cases of the example: 1. in the first test case, it's possible to remove two characters from the beginning and one character from the end. Only one 1 is deleted, only one 0 remains, so the cost is $ 1 $ ; 2. in the second test case, it's possible to remove three characters from the beginning and six characters from the end. Two characters 0 remain, three characters 1 are deleted, so the cost is $ 3 $ ; 3. in the third test case, it's optimal to remove four characters from the beginning; 4. in the fourth test case, it's optimal to remove the whole string; 5. in the fifth test case, it's optimal to leave the string as it is.

**题目大意**：

给定一个由字符 '0' 和 '1' 组成的字符串 $ s $。你可以从字符串的开头和结尾移除若干个字符（可以是零个），字符串可能会因此变空。移除操作的代价是字符串中剩余的 '0' 的数量和被移除的 '1' 的数量中的较大值。求能够实现的最小移除代价。

**输入格式**：

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

接下来 $ t $ 行，每行包含一个字符串 $ s $（$ 1 \le |s| \le 2 \cdot 10^5 $），由字符 '0' 和 '1' 组成。

所有测试用例中字符串 $ s $ 的总长度不超过 $ 2 \cdot 10^5 $。

**输出格式**：

对于每个测试用例，输出一行，包含一个整数，表示能够实现的最小移除代价。

**输入输出样例**：

**输入样例 #1**:
```
5
101110110
1001001001001
0000111111
00000
1111
```

**输出样例 #1**:
```
1
3
0
0
0
```

**说明**：

样例解释：

1. 在第一个测试用例中，可以移除开头的两个字符和结尾的一个字符。这样只有一个 '1' 被删除，只有一个 '0' 剩余，所以代价是 1；
2. 在第二个测试用例中，可以移除开头的三个字符和结尾的六个字符。这样有两个 '0' 剩余，三个 '1' 被删除，所以代价是 3；
3. 在第三个测试用例中，最优的做法是移除开头的四个字符；
4. 在第四个测试用例中，最优的做法是移除整个字符串；
5. 在第五个测试用例中，最优的做法是保持字符串不变。**题目大意**： 给定一个由字符 '0' 和 '1' 组成的字符串 $ s $。你可以从字符串的开头和结尾移除若干个字符（可以是零个），字符串可能会因此变空。移除操作的代价是字符串中剩余的 '0' 的数量和被移除的 '1' 的数量中的较大值。求能够实现的最小移除代价。 **输入格式**： 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。 接下来 $ t $ 行，每行包含一个字符串 $ s $（$ 1 \le |s| \le 2 \cdot 10^5 $），由字符 '0' 和 '1' 组成。 所有测试用例中字符串 $ s $ 的总长度不超过 $ 2 \cdot 10^5 $。 **输出格式**： 对于每个测试用例，输出一行，包含一个整数，表示能够实现的最小移除代价。 **输入输出样例**： **输入样例 #1**: ``` 5 101110110 1001001001001 0000111111 00000 1111 ``` **输出样例 #1**: ``` 1 3 0 0 0 ``` **说明**： 样例解释： 1. 在第一个测试用例中，可以移除开头的两个字符和结尾的一个字符。这样只有一个 '1' 被删除，只有一个 '0' 剩余，所以代价是 1； 2. 在第二个测试用例中，可以移除开头的三个字符和结尾的六个字符。这样有两个 '0' 剩余，三个 '1' 被删除，所以代价是 3； 3. 在第三个测试用例中，最优的做法是移除开头的四个字符； 4. 在第四个测试用例中，最优的做法是移除整个字符串； 5. 在第五个测试用例中，最优的做法是保持字符串不变。