牛客小白月赛4-I-合唱队形

https://www.nowcoder.com/acm/contest/134/I

    做法，2个人交换位置肯定是男和女交换，枚举全部男生就可以了。

    一共就三种情况，第一种是n个人全部是女生，那最长连续女生就是n了，第二种是，当前枚举到的男生，左边连续女生的个数+右边连续女生的个数等于总的女生数量，连续长度就是l[i-1]+r[i+1],第三种是，当前枚举到的男生，左边连续女生的个数+右边连续女生的个数不等于总的女生数量，那就可以拿这2个联通块以外的女生和该男生交换位置，连续长度为l[i-1]+r[i+1]+1

l[i]表示：当i位置为男生时为值0，当为女生时表示此女生为从左往右连续女生的最后一个，值为连续女生的个数。r[i]也是一样

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n,wn=0,mx=0;
char s[maxn];
int l[maxn],r[maxn]；
int main()
{
    cin>>n>>s+1;
    l[0]=0;
    r[n+1]=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='0')
        {
            l[i]=l[i-1]+1;
            wn++;
        }
        else
            l[i]=0;
    }
    for(int i=n;i>=1;i--)
    {
        if(s[i]=='0')
        {
            r[i]=r[i+1]+1;
        }
        else
            r[i]=0;
    }
    
    if(n==wn) {cout<<wn<<endl; return 0;}
    for(int i=1;i<=n;i++)
        if(s[i]=='1')
        {
            if((l[i-1]+r[i+1])==wn)
                mx=max(mx,l[i-1]+r[i+1]);
            else
                mx=max(mx,l[i-1]+r[i+1]+1);
        }
    cout<<mx<<endl;
    return 0;

}