求救！！！（解出必给解决方案）

常规
1

题目描述

给定一个长度为 n 的 01 字符串。你需要从前面删去若干个字符（可以为 0 个），再从后面删去若干个字符（可以为 0 个），使得以下两者较大的一个尽可能小：

  • 删去的 1 的个数。
  • 留下的 0 的个数。注意你可以删空整个串。

输入格式

第一行一个整数 T，表示数据组数，

每组数据一行一个 01 字符串。

输出格式

每组数据输出一行，代表代价的最小值。

样例输入

5
101110110
1001001001001
0000111111
00000
1111

样例输出

1
3
0
0
0

数据规模

1≤T≤1041≤T≤104，1≤∣s∣≤2×1051≤∣s∣≤2×105，∑∣s∣≤2×105∑∣s∣≤2×105。

1 个赞
3

二分+双指针

1 个赞
4

先处理前缀和数组
然后二分

1 个赞
5

这么说吧：二分综合
二分它的代价

思路：
先用两个数组统计所有01个数（前缀和）
然后二分代价：

while(...){
    int mid=...
    (check(mid,len)?r=mid:l=mid)
}

check里：
是个双指针，先找两个区间内的0个数，如果个数一直小于等于当前的价值，左指针就往左找
然后再看1~左指针和右指针~n的1个数是否合法，合法就return true，如果一直不合法就return false

1 个赞
6 
#include<bits/stdc++.h>
using namespace std;
int k;
char xx[200001];
int s[200001];
int ss[200001];
bool f(int m,int n){
	for(...){
		while(...){
			y--;
		}
		if(...){
			return true;
		}
	}
	return false;
}
int main(){
	...
}
1 个赞