【菜笔cf刷题日常-1600】C.BinaryString（二分求min/max）

链接： codeforces /contest/1680/problem/C

题意：给一段01组成的字符串序列，要求从前面和从后面删去一段连续字符后，使以下两值的最大值：

字符串中剩余的字符数 0；从字符串中删除的字符数 1

最小的答案

思路：使用二分。判断：已知答案大于等于 字符串中剩余的字符数 0 和 从字符串中删除的字符数 1 ，先建立 pos 数组记录 1 的位置，用前缀和记录 0 ，每次枚举（ 1 的总数 - 答案 ）个连续 1 中间 0 的个数，如果小于等于答案，则成立

code：

#include<bits/stdc++.h> #define int long long using namespace std; int n,m,t,k,l,r,q,p,x,idx,res,cnt,sum,flag,maxx,minn; const int N=200010; const int MOD=1e9+7; const int INF=0x3f3f3f3f3f3f3f3f; int a[N],b[N],c[N],d[N]; string s; vector<int> pos; bool check(int mid){ if(mid==pos.size())return 1; flag=0; int tem=pos.size()-mid-1; for(int i=0;i<pos.size()-tem;i++){ if(a[pos[i+tem]]-a[pos[i]]<=mid){ flag=1; break; } } return flag; } void solve(){ cin>>s; s=" "+s; pos.clear(); for(int i=1;s[i];i++){ a[i]=a[i-1]+(s[i]=='0'); if(s[i]=='1'){ pos.push_back(i); } } l=0,r=pos.size(); if(check(l)){ cout<<l<<'\n'; return; } while(l+1<r){ int mid=(l+r)/2; if(check(mid)){ r=mid; } else l=mid; } cout<<r<<'\n'; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>t; while(t--)solve(); return 0; }