南邮 OJ 1574 男女配对

男女配对

比赛描述

距 Alice 观察，身高相近的人似乎比较合得来。Alice 在学校策划了一次大型的“ 非常男女” 配对活动。对于这次活动的参与者， Alice 有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。Alice 当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。

输入

第一行有一个正整数 n，代表学校的人数。

第二行有 n 个用空格隔开的数，这些数只能是 0 或 1，其中， 0 代表一个女生， 1代表一个男生。 n<=100 000。

输出

输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子序列长度。

如果不存在男女人数相等的子序列，请输出 0。

样例输入

9
0 1 0 0 0 1 1 0 0

样例输出

6

提示

样例说明：选择第 2 个人至第 7 个人可以获得男女人数均为 3 的最长子序列。

题目来源

NUPT ACM

//c[i]表示前i个人中男生比女生多的个数
//f[i]表示第一次出现男生比女生多 i 个的位置，以后在遇到时，相减就是人数#include
#define N 100001
int c[N],f[N<<1];int main(){int n,i,num,maxV,temp;scanf("%d",&n);maxV = 0;c[0] = N;for(i=1;i<=n;i++){scanf("%d",&num);if(1==num){c[i] = c[i-1]+1;}else{c[i] = c[i-1]-1;}if(N==c[i]){if(maxV < i){maxV = i;}}else{if(!f[c[i]]){f[c[i]] = i;}else{if(maxV < (temp=i-f[c[i]])){maxV = temp;}}}}printf("%d\n",maxV);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！