[C++知识库]Educational Codeforces Round 128 (Rated for Div. 2) Problem C Binary String（二分答案+双指针）

题目
题意
给定一个01字符串，你可以选择在这个字符串的头部和尾部删除多个字符（包括0个），字符串具有价值，他的价值取决于max(删除的字符里1的个数，剩下的字符串里0的个数），求最小价值
思路
对字符串里剩余0的个数进行二分，
用前缀和记录字符串0和1的个数，
利用双指针处理头部，尾部，中间，这三个区间。
代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> PII;
int s0[maxn],s1[maxn];
int cnt0,cnt1;
int n;

int cal(int l,int r)//取剩下0的个数，和删除1的个数最大值
{
    return max(s0[r]-s0[l-1],s1[l-1]+s1[n]-s1[r]);
}

bool check(int x)
{   
    int sum=inf;
    for(int l=1,r=0;l<=n;l++)//双指针，因为也可以不删，所以r从0开始
    {
        sum=min(sum,cal(l,r));
        while(s0[r]-s0[l-1]<=x&&r<n)//如果该区间剩下的0的个数，还到不了二分里0的个数，继续扩大区间
        {
            r++;
            sum=min(sum,cal(l,r));
        }
    }
    return sum<=x;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        n=s.size();
        cnt0=cnt1=0;
        for(int i=0;i<s.size();i++)//前缀和
        {
            if(s[i]=='0')
            {
                s0[i+1]=s0[i]+1;
                s1[i+1]=s1[i];
                cnt0++;
            }
            else
            {
                s1[i+1]=s1[i]+1;
                s0[i+1]=s0[i];
                cnt1++;
            }
        }
        int l=0,r=cnt0;
        int ans=inf;
        while(l<=r)//对剩下字符串0的个数进行二分
        {
            int mid=l+r>>1;
            if(check(mid))
            {
                ans=min(ans,mid);
                r=mid-1;
            }
            else
            l=mid+1;
        }
        cout<<ans<<endl;
    }
}

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系