洛谷1114 “非常男女”计划
本题地址：http://www.luogu.org/problem/show?pid=1114
题目描述
近来，初一年的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) 最简单的想法就是遍历所有的子串，之后判断该子串是否满足条件。（就像寻找最大子序列一样。）有 N^2子串，每个子串扫一遍判断0、1是否出现的次数相等，复杂度为O(N^3)。
进一步思考就会发现， 如果一个长度为n的子串满足条件，加么这n个元素的和 加起来一定=(n/2)，这样在循环的过程中，增量加就可以了，不需要每个子串从头计算，复杂度降为O(N^2)。
（嗯，这个地方的改进其实就是最大子序列和问题当中O（N^2）级别算法的类似改进。）
最大子序列和问题：http://www.cnblogs.com/huashanqingzhu/p/3861238.html
上述解决最大子序列和问题的两个算法：（下面三张图片截取自浙大陈越老师的PPT）
（2）为了进一步降低算法的时间复杂度，引入相对差的概念。即a[i]表示第i个位置男生人数-女生人数的差值。
那么差值相等的两个位置之间的人数是满足男女相等的。因此，统计l[a[i]]和r[a[i]]即可。特别要注意的是a[0]=0。
统计的时候要把0的位置当做差为0的起点。
上述这段话是原题目网站的提示，思考半天，没太理解。
（试想：在含有n个元素的整数序列中寻找两个距离最远而且相等的元素，时间复杂度似乎也是平方级别的。）
后来看到网络上有人对这个题的类似题目做了一个简单的解析：
http://www.cnblogs.com/worldisimple/archive/2012/04/13/2445051.html
摘抄原文部分：
原文作者对此给出的比较好的解决思路：
对于原文作者伪代码的错误和不严谨，我就不说了。
重要的是，看了分析，大概明白了如何用O（n）的时间复杂度完成“在含有n个元素的整数序列中寻找两个距离最远而且相等的元素”这样一个问题。
但是，该文章的作者没注意到：统计的时候要把0的位置当做差为0的起点。修改了文章作者的代码，得到如下的AC代码：
#include <stdio.h>
#include<stdlib.h>
int main()
{
int n,t;
int *b,*num;
int count[]={,};//统计从第一个到第i个位置的子段中，0和1的个数
int maxlen=,currlen=;
int i;
scanf("%d",&n);
b=(int *)malloc((n+)*sizeof(int));
num=(int *)malloc((n*+1)*sizeof(int));
for(i=;i<=n;i++)
b[i]=; //b[i]用于记录0-1序列的前i个值中，0和1的个数之差
for(i=;i<=*n+;i++)
num[i]=-; //num[]用于统计记录b[]各元素首次出现的下标。比如b[i]==x，而且i是x在b[]首次出现的位置，则num[b[i]+n]=i。num[i]默认值-1. for(i=;i<=n;i++)
{
scanf("%d",&t); //输入一个数字：0或1
count[t]++; //统计0和1的个数
b[i]=count[]-count[];//b[i]保存0-1序列的前i个元素中：0和1的个数之差
}
if(count[]==count[]) printf("%d\n",count[]+count[]);
else
{
for(i=;i<=n;i++)//注意：从0和1的个数都是0的地方开始扫描
{
if(num[b[i]+n]==-) //检测b[i]的值是否曾经在b[]出现过。num[b[i]+n]== -1表示b[i]没有出现过
num[b[i]+n]=i; //记录b[i]的值在b[]首次出现的位置i
else//already exist
{
currlen = i - num[b[i]+n] ; //num[b[i]+n]是b[i]首次出现的下标
if(currlen > maxlen)
maxlen = currlen;
}
}
printf("%d\n",maxlen);
} free(b);
free(num);
return ;
}