P1114 “非常男女”计划【洛谷算法习题】

P1114 “非常男女”计划网页链接P1114 “非常男女”计划题目描述近来初一年的XXX小朋友致力于研究班上同学的配对问题别想太多仅是舞伴通过各种推理和实验他掌握了大量的实战经验。例如据他观察身高相近的人似乎比较合得来。万圣节来临之际XXX准备在学校策划一次大型的 “非常男女” 配对活动。对于这次活动的参与者XXX有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排然后从中选出连续的若干个人使得这些人中男女人数相等。为了使活动更热闹XXX当然希望他能选出的人越多越好。请编写程序告诉他他最多可以选出多少人来。输入格式第一行有一个正整数n ( 1 ≤ n ≤ 10 5 ) n\ (1\le n \le 10^5)n(1≤n≤105)代表学校的人数。第二行有n nn个用空格隔开的数这些数只能是0 00或1 11其中0 00代表是一个女生1 11代表是一个男生。输出格式输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子区间的长度。如果不存在男女人数相等的子区间请输出0 00。输入输出样例 #1输入 #19 0 1 0 0 0 1 1 0 0输出 #16解题思路本题核心是前缀和差值位置记录求解最长男女数量相等的连续子区间是经典的平衡子数组问题。将男生记为1、女生记为0计算男女数量的差值若两个位置的差值相同则这两个位置之间的子区间男女数量相等。为避免数组下标为负将差值整体偏移n用两个数组分别存储每个差值第一次和最后一次出现的下标。遍历完成后计算所有差值对应末次下标与首次下标的差最大值即为答案。该算法仅需线性遍历一次数组时间复杂度O ( n ) O(n)O(n)完美适配n ≤ 10 5 n \le 10^5n≤105的大数据规模。总结核心逻辑利用男女数量差值的相等性定位平衡连续子区间取最长长度。关键操作偏移处理负数下标记录每个差值的首次、末次出现位置计算最大区间长度。效率保障线性时间复杂度无冗余计算高效处理题目最大数据限制。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N2e510;constll p1e97;constll INF1e18;constll M5e310;ll l[N],r[N];intmain(){ll n;cinn;ll sum00,sum10;for(ll i1;in;i){ll x;cinx;sum1(x1),sum0(x0);ll tsum0-sum1n;if(!l[t]t!n)l[t]i;elser[t]i;}ll ans0;for(ll i0;i2*n;i)ansmax(ans,r[i]-l[i]);coutansendl;return0;}