A50246.午枫的01串翻转 题解

如果字符串没有 0，那么显然答案为 $0$；

如果字符串只有 $1$ 个 0，那么我们要争取做一次操作让 0 变多。考虑到 $r$ 的位置一定会变成 0，所以如果 $r$ 越靠后，距离越远。统计 0 后面的 1 的位置，如果少于 $2$ 个则无可奈何，否则选择最后一个 1 与最前的一个 1 即可。

如果字符串有 $2$ 个或者更多 0，那么显然，我们至少可以将其中之一作为 $l$。第一个 0 显然是需要我们保留下来作为最远距离的，所以我们选择其他的任意一个 0 作为 $l$。如果结尾是 0，那么无需操作也能得到最远距离；如果结尾是 1，那么令其为 $r$​，一次操作之后，结尾又会变成 0。综上所述，我们需要的 0 一定是第一个 0 和结尾。

时间复杂度：$O(n)$

空间复杂度：$O(n)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,l,r,ans;
string s;
vector<ll> v;
int main(){
    cin>>n>>s;
    if(count(s.begin(),s.end(),'0')==0){
        cout<<0;
        return 0;
    }
    if(count(s.begin(),s.end(),'0')==1){
        l=s.find('0');
        for(ll i=l+1;i<n;i++) if(s[i]=='1') v.push_back(i);
        if(v.size()<=1) cout<<0;
        else cout<<v.back()-l-1;
        return 0;
    }
    cout<<n-1-s.find('0');
    return 0;
}