官方题解

T4 午枫的又一个01串

题目大意

给定一个 $01$ 串，这个串的度为相邻两位元素不相同的个数，可以进行指定操作最多 $m$ 次，求出最小度是多少。

解题思路

对于一个 $01$ 串，如果我们进行的操作区间不在开头也不在结尾，即 $[l,r]$ 满足 $1<l<r<n$ ，不难 $s_l$ 和 $s_{l-1}$ 从不同变为相同，$s_r$ 和 $s_{r+1}$ 从不同变为相同。所以当我们对中间部分操作一次，度就会减 $2$ 。

考虑完中间部分操作的影响，接下来考虑开头和结尾操作会有什么影响：

如果开头 $s_1=1$ ，则无法操作，同理，如果结尾 $s_n=0$ 也无法操作。

如果开头 $s_1=0$ ，我们对区间 $[1,r]$ $(1<r<n)$ 做一次操作后，由于 $s_1$ 前面没有数字了，原本就没有度，所以左端点的改变不会的度产生影响，$s_r$ 和 $s_{r+1}$ 从不同变为相同，因此此次操作会让度减少 $1$ 。同理，对结尾 $s_n=1$ ，做一次操作也会让度减少 $1$ 。

因此，先求出原串的度，优先对串的中间部分进行操作，在判断开头结尾的情况做出相应操作，计算度的减少量即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int n,m;cin>>n>>m;
    string s;cin>>s;s=' '+s;
    if(n==1){
        cout<<0<<endl;
        return;
    }

    int cnt=0;
    for(int i=1;i<n;i++){
        if(s[i]!=s[i+1]) cnt++;
    }

    if(cnt<2){
        cout<<cnt<<endl;
        return;
    }

    int ex=0;
    if(s[1]=='0') ex++;
    if(s.back()=='1') ex++;

    int need=0;
    need=(cnt-ex)/2;
    if(m>=need+ex) cout<<min(1ll,cnt)<<endl;
    else{
        if(ex==0) cout<<cnt-2*m<<endl;
        else if(ex==1){
            if(m<=need) cout<<cnt-2*m<<endl;
            else cout<<cnt-2*need-min(ex,m-need)<<endl;
        }
        else if(ex==2){
            if(m<=need) cout<<cnt-2*m<<endl;
            else cout<<cnt-2*need-min(ex,m-need)<<endl;
        }
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}