147的字符串
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
147学长最近获得了一个由字符 0 和 1 组成的字符串S。他对这个字符串很是喜爱,以至于他总想对这个字符串做点什么
于是,147想到了一个骚操作:
147从字符串的开头删除了几个(可能是零个)字符,然后又从字符串的末尾删除了几个(可能是零个)字符。删除后,字符串可能会变为空。147是一个做事总是考虑成本的人,所以他定义删除的成本是以下两个值中的最大值:
- 字符串中剩余的字符0的个数;
- 从字符串中删除的字符1的个数。
请问147可以达到的最小删除成本是多少?
输入形式
第一行包含一个整数t () — 测试用例的数量。
每个测试用例由一行由一个字符串S组成(),由字符 0 和 1 组成。
|S|表示字符串S的长度
保证每个测试样例的字符串的总长度不会超过
输出形式
对于每个测试用例,打印一个整数 — 147可以实现的最小删除成本。
样例
5
101110110
1001001001001
0000111111
00000
1111
1
3
0
0
0
样例解释
在第一个测试用例中,可以从开头删除两个字符,从末尾删除一个字符。只有一个 1 被删除,只剩下一个 0,所以成本是1;
在第二个测试用例中,可以从开头删除三个字符,从末尾删除六个字符。保留两个字符 0,删除三个字符 1,因此成本为3;
在第三个测试用例中,最好从开头删除四个字符;
在第四个测试用例中,最好删除整个字符串;
在第五个测试用例中,最好将字符串保持原样。
2022ACM新生积分赛 Round #4
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 11
- 开始于
- 2022-11-5 13:00
- 结束于
- 2022-11-5 18:00
- 持续时间
- 5 小时
- 主持人
- 参赛人数
- 56