← 返回题目列表

Codeforces · 1680/C

C. 二进制字符串

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

给定一个由字符 0 和/或 1 组成的字符串 $$$s$$$。

您必须从字符串开头删除几个(可能为零)字符,然后从字符串末尾删除几个(可能为零)字符。删除后字符串可能会变空。移除成本是以下两个值中的最大值:

- 字符串中剩下的字符0的数量;
- 从字符串中删除的字符数 1。

您能实现的最低移除成本是多少?

输入

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

每个测试用例由一行包含字符串 $$$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. 在第五个测试用例中,最好保持字符串不变。