J. P1114 “非常男女”计划
这道题容易想到\(n^3\)的做法(先枚举长度,再枚举起点,最后check)
进一步优化想到可以使用前缀和\(s[i]\)表示前\(i\)个位置有\(s[i]\)个男生,只要s[i]*2==i即可满足题意,此时时间复杂度为\(n^2\)(枚举起点和终点)
这样应该是能拿到60分. 遂查阅题解.
正解如下:
记录一下前i个人中男生和女生的差值.可以想一下如果前i个位置差值与前j个位置的差值是一样的,是不是就说明\([i+1,j]\)这段区间男女生的个数是一样的了.
如果位置\(j\)的男生个数-女生个数为\(s[j]\),只需要找前面的位置i处\(s[i]==s[j]\)即为满足题意.
用unordered_map存一下值为s[j]时的最早下标就好了.
点击查看代码
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define endl '\n'
using namespace std;
unordered_map<int,int> m;
const int N = 1e5+10;
int n;
int a[N];
int s[N];
int man,woman;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int res = 0;
m[0] = 0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
man+=a[i]==1;
woman+=a[i]==0;
s[i] = man-woman;
if(m.find(s[i])==m.end())
{
m[s[i]]= i;
}
else
{
res = max(res,i-m[s[i]]);
}
}
cout<<res;
return 0;
}