官方题解

T4 午枫的01串翻转

题目大意

给定一个 $01$ 串，可以进行指定操作，求出所有可能的 $01$ 串中距离最远的两个 $0$ 的距离是多少。

题解思路

我们其实最多只需要操作一次即可得到答案。

一共分三种情况：

• 没有 $0$ ，直接输出 $0$ 。
• 只有一个 $0$ ，此时很容易发现不操作的话距离一定是 $0$ ，所以我们尽量考虑操作。
  • 如果这个 $0$ 在最后两个位置，要么无法操作，要么操作了一次也还是只能有一个 $0$ , 此时答案为 $0$ .
  • 如果不在最后两个位置，考虑到其余位置都为 $1$ ，我们尽量操作更长的区间，能使两个 $0$ 的距离最大，那么以这个 $0$ 为区间左端点，最后一个 $1$ 为区间右端点，对这段区间进行一次操作，就会将区间内所有的 $1$ 都变为 $0$ ，此时答案为 $翻转区间长度-1$ .
• 有两个及以上个 $0$ ，此时我们可以让最左端的 $0$ 不动，记这个 $0$ 的位置为 $pos$ ，用后面的任意 $0$ 最为操作区间的左端点，最后一个 $1$ 最为区间右端点，不难发现，操作后距离最左端的 $0$ 最远的 $0$ 一定是最后一个字符，此时答案为 $n-pos$ .

综上所述，此题只需找到第一个 $0$ 的位置，按照上述情况分类讨论即可。

参考代码

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

void solve(){
    int n;cin>>n;
    string s;cin>>s;s=' '+s;
    int cnt=0;
    for(auto c:s){
        if(c=='0') cnt++;
    }
    if(cnt==0){
        cout<<"0"<<endl;
        return;
    }

    int pos=s.find('0');
    if(cnt==1){
        if(pos>n-2) cout<<0<<endl;
        else cout<<n-pos-1<<endl;
    }
    else cout<<n-pos<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}