[Luogu] P1114 “非常男女”计划

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;
}