“非常男女”计划
題目描述
近來，初一年的XXX小朋友致力于研究班上同學的配對問題（別想太多，僅是舞伴），通過各種推理和實驗，他掌握了大量的實戰經驗。例如，據他觀察，身高相近的人似乎比較合得來。
萬圣節來臨之際，XXX準備在學校策劃一次大型的“非常男女”配對活動。對于這次活動的參與者，XXX有自己獨特的選擇方式。他希望能選擇男女人數相等且身高都很接近的一些人。這種選擇方式實現起來很簡單。他讓學校的所有人按照身高排成一排，然后從中選出連續的若干個人，使得這些人中男女人數相等。為了使活動更熱鬧，XXX當然希望他能選出的人越多越好。請編寫程序告訴他，他最多可以選出多少人來。
輸入輸出格式
輸入格式：
第一行有一個正整數n，代表學校的人數。n<=100000
第二行有n個用空格隔開的數，這些數只能是0或1，其中，0代表一個女生，1代表一個男生
輸出格式：
輸出一個非負整數。這個數表示在輸入數據中最長的一段男女人數相等的子序列長度。
如果不存在男女人數相等的子序列，請輸出0。
輸入輸出樣例
輸入樣例#1：
9
0 1 0 0 0 1 1 0 0
輸出樣例#1：
6
.
.
.
.
.
.
.
分析
采用賦值法，將男賦值為1，女為-1，記錄一下前綴和
我們可以從1到n掃過去，看看前面有沒有和我們相同的前綴和（這樣減掉的話男女數量就相等了），我用map【i】數組記錄i這個前綴和出現的最早位置
注意：由于c++數組下標不能為負，所以都加上n；前綴和為0特殊處理，因為我那個map【i】=0的時候是當沒出現過的，不然map[0]=0也會當沒出現過。
.
.
.
.
.
.
.
程序：
#include<iostream> #include<cstdio> using namespace std; int a[100001],Map[200001],sum[200001],n,i,ans; int main() {scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d",&a[i]); if (a[i]==0) a[i]=-1; sum[i]=sum[i-1]+a[i];}for (i=1;i<=n;i++){if (sum[i]==0){ans=max(ans,i);continue;}if (Map[sum[i]+n]&&ans<i-Map[sum[i]+n]) ans=i-Map[sum[i]+n];if (Map[sum[i]+n]==0) Map[sum[i]+n]=i;}cout<<ans<<endl; }轉載于:https://www.cnblogs.com/YYC-0304/p/9499971.html
總結
