https://www.luogu.com.cn/problem/P1114
暴力，前缀和，稍加优化可以拿100，但是#1加强过后就AC不了了
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6;
int a[maxn],n,f[maxn],ans,boy;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
boy+=a[i];
f[i]=a[i]+f[i-1];
}
if(boy==n)
{
cout<<0;
return 0;
}
for(int i=1;i<=n;i++)
{
for(int j=i+ans;j<=n;j++)
{
if((j-i+1)==(f[j]-f[i-1])*2) ans=max(ans,(j-i+1));
}
}
cout<<ans<<endl;
return 0;
}
打开题解，看到点赞第一的大佬
引入相对差的概念。即a[i]表示第i个位置男生人数-女生人数的差值。
那么差值相等的两个位置之间的人数是满足男女相等的。
从此统计l[a[i]]和r[a[i]]。
特别要注意的是a[0]=0 统计的时候要把0的位置当做差为0的起点。
所以写出如下代码（当时困得要死，借鉴了一下二楼 逃）
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5;
int l[maxn],r[maxn],a[maxn],n,ans,boy,girl;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
boy+=t;girl+=!t;
a[i]=boy-girl+n;
if(l[a[i]]==0 && a[i]!=n) l[a[i]]=i;
else r[a[i]]=i;
}
for(int i=0;i<=2*n;i++) ans=max(ans,r[i]-l[i]);
cout<<ans<<endl;
return 0;
}