这道题是前缀和的简单应用。
我们可以将男生看为1,女生看为-1。那么题目要求的最长子数组的判断条件为该数组和是否为0。
首先我们对整个数组进行前缀和;
接下来假定该最长子数组在right位置(right进行遍历)结束,那么就有两种情况讨论:
1、该位置前缀和为0,那么与max进行比较。
2、该位置前缀和为1或-1,那么找到最左边前缀和同样为1或-1的位置left,将right-left与max比较。
主要代码:
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N]; int main(){ int n,max_=0; cin>>n; map<int,int> map1; map1[0]=0; for (int i=1;i<=n;i++){ cin>>a[i]; a[i]=a[i]==1 ? 1 :-1; a[i]+=a[i-1]; if (map1.count(a[i])){ max_=max(max_,i-map1[a[i]]); } else map1[a[i]]=i; } cout<<max_; return 0; }
标签:right,P1114,前缀,int,max,map1,计划,男女,数组 From: https://www.cnblogs.com/purple123/p/18008428