贴个二分代码，跑得比spq的O(N)做法快
思路： 假设1的数量是$c$。如果答案是$x$，那么我们最多删除了$x$个1，并且最多留下了$x$个0。如果$c \ge x+1$，一定满足要求。因此，答案存在单调性，我们考虑对区间$[0, c]$使用二分。

我们实现一个数组$pos$，其中$pos_i$是字符串中第$i$个1的位置。在$check$函数中，我们枚举每个删完后剩下的区间，并判断其中0的个数是否$\le x$。
核心代码：

signed main()
{
	setIO();
	string str; cin>>str;
	vector<int> pos;
	for(int i=0; i<str.size(); i++)
		if(str[i]=='1')
			pos.eb(i);
	if(pos.empty() || pos.back()-pos.front()==pos.size()-1)
		return cout<<0<<endl, 0;
	int l=0, r=pos.size(), res=r;
	auto check=[&](int mid) -> bool
	{
		int k=pos.size(), x=k-mid;
		for(int i=0; i<=mid; i++)
		{
			int l=pos[i], r=pos[i+x-1];
			if(r-l+1-x<=mid)
				return true;
		}
		return false;
	};
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid-1, res=mid;
		else l=mid+1;
	}
	cout<<res<<endl;
	return 0;
}

这里有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;
}

分析

tag:二分、滑动窗口

由于两个操作是从两端删除任意长度，所以本质就是保留一个子串，问题转化为找到一个子串，使得$max($长度- 子串中$1$数量,子串中$0$的数量$)$最小，我们二分答案，维护一个滑动窗口。二分答案区间为$[0,cnt0]$，一眼看去我们应该取$max(cnt0,cnt1)$为右端点，对于一个子串当你删掉的$1$少于$0$的时候，那你为何不能再删多几个$1$达到和剩余的$0$相同数目，还说不定能删更多的$0$呢导致更优的答案，所以对于初始字符串二分的答案区间为$[0,cnt0]$，也就是子串最多能剩多少个$0$。$check$的话维护一个滑动窗口，当当前窗口$0$的数量超过了$mid$就左端点右移，对于每个窗口统计答案，判断剩下的$1$是否也小于等于$mid$，也就是是否符合$max(del1,cnt0) \leq mid$，不符合的话取右边区间，符合的话记录答案并且取左区间。

参考代码

#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 10;
char s[N];
int n;
bool check(int mid, int tot1) {
    int l = 0;
    int cnt0 = 0, cnt1 = 0;
    for (int r = 0; r < n; r++) {
        if (s[r] == '1') {
            cnt1++;
        } else {
            cnt0++;
        }
        while (cnt0 > mid) {
            if (s[l] == '1') {
                cnt1--;
            } else {
                cnt0--;
            }
            l++;
        }
        int del1 = tot1 - cnt1;
        if (del1 <= mid) {
            return true;
        }
    }
    return false;
}


int main() {
    scanf("%s", s);
    n = strlen(s);
    int cnt1 = 0;
    for (int i = 0; i < n; i++) cnt1 += s[i] - '0';
    int cnt0 = n - cnt1;
    int l = 0, r = cnt0;
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid, cnt1)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}