#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[200005],t,n;
string s;
bool check(int mid){
int cnt0=0;
for(int i=1,j=1;i<=n;i++){
while(j-1<=n&&cnt0<=mid){
cnt0+=(s[j-1]=='0');
j++;
}
cnt0-=(s[i-1] == '0');
if(a[i-1]+a[n]-a[j-1]<= mid) return true;
}
return false;
}
signed main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
cin>>t;
while(t--){
cin>>s;
n=s.size();
for(int i=0;i<n;i++){
if(s[i]=='0')a[i+1]=a[i]+1;
else a[i+1]=a[i];
}
int l=0,r=n-1;
while(l!=r){
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<"\n";
}
return 0;
}
a[i]求的应该是1的个数
1 个赞
check中双指针的j的判断条件是j <= n
1 个赞