这里有o(n)解法：

共n个01字符 设其中共cnt个"0"，最佳删s个数，其中删t个"1". 那么剩下的0即可表示为cnt-s+t。 那么题意就是求max(t,cnt-s+t)。 将t提出 即求t+max(0,cnt-s)。

现在可以猜想结论：在s=cnt时最优，下证： 当s取cnt-1时： max部分一定增大1 而t部分可能减小一也可能不减小 因此当s取小于cnt时一定不更优。 当s取cnt+1时： t部分可能增大一也可能不增大 而max部分一定减小 因此当s取大于cnt时一定不更优。 综上 s=cnt时一定最优。

运用结论 暴力o(n^2)即可优化为o(n)。

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
long long n;
string s;
int cnt=0;
int f[N];
int a[N];
int b[N];
int ans=INT_MAX;
int main(){
	cin>>s;
	n=s.length();
	for(int i=0;i<n;i++){
		f[i+1]=s[i]-'0';
		if(s[i]=='0'){
			cnt++;
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i]==1){
			a[i]++;
		}
		a[i]+=a[i-1];
	}
	for(int i=n;i>=1;i--){
		if(f[i]==1){
			b[i]++;
		}
		b[i]+=b[i+1];
	}
	for(int i=0;i<=cnt;i++){
		ans=min(ans,a[i]+b[n-cnt+i+1]);
	}
	cout<<ans;
	return 0;
}