合唱队形(悬线法）

链接：https://ac.nowcoder.com/acm/contest/134/I
来源：牛客网

铁子的班级在毕业晚会有一个合唱节目，到了毕业晚会的时候，他们必须排成一排一起合唱"认错"，"当然是选择原谅他"等一系列原谅歌曲，但是当队形布置好的时候，领导们觉得队形里最长的连续的女生的长度太小了，但是由于马上要开始演唱，所以最多只能两个人交换位置，问新队形中最长的连续的女生的长度是多少？

输入描述:

第一行一个数字n表示铁子班级的总人数。1≤n≤10

⁵

第二行一个字符串s表示最初的队形布置，si=0表示第i个人是女生，si=1表示第i个人是男生。

输出描述:

输出一行表示答案

示例1

输入

复制

6
101010

输出

复制

3

说明

将第6个女生和第3个男生交换位置可以满足要求



这个题和悬线法差不多

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int l[maxn],r[maxn];
int main(){
    int n;
    cin>>n;
    scanf("%s",a+1);
    int len=strlen(a+1); 
    int z=0;
    for(int i=1;i<=len;i++){
        if(a[i]=='0'){
            l[i]=l[i-1]+1;
            z++;
        }
    }
    for(int i=len;i>=1;i--){
        if(a[i]=='0'){
            r[i]=r[i+1]+1;
        }
    }
    if(z==len){
        cout<<len<<endl;
    } 
    else{
        int ans=0;
        for(int i=1;i<=len;i++){
            if(a[i]=='1'){
                if(l[i-1]+r[i+1]==z){//因为要交换嘛
                    ans=max(ans,l[i-1]+r[i+1]);
                }
                else{ 
                    ans=max(ans,l[i-1]+r[i+1]+1);
                } 
            }
        }
        cout<<ans<<endl;
    }
}