思路：使用a存前缀和。遇见女生-1，遇见男生+1。之后遍历a的时候，如果a[i]=a[j]，则说明ij这个区间里男女生数量是一样的。所以即求ij这个区间最大长为多少。可以用l[]r[]数组记录某个数第一次出现的位置和最后一次出现的位置。
例如样例：a[]=-1 0 -1 -2 -3 -2 -1 -2 -3
则
l[-1]=1 r[-1]=7
l[0]=2 r[0]=2
l[-2]=4 r[-2]=6
l[-3]=5 r[-3]=9
所以答案为7-1=6
代码：
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, sum[N], l[N * 2], r[N * 2], ans; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> m; // 0女1男 if (m == 0) { sum[i] = sum[i - 1] - 1; } else { sum[i] = sum[i - 1] + 1; } int tmp = sum[i] + n; // sum[i]的范围是-n到n，矫正保证为正数 if (l[tmp] == 0) { l[tmp] = i; } else { r[tmp] = i; } } for (int i = 0; i < 2 * n; i++) { ans = max(ans, r[i] - l[i]); } cout << ans; return 0; }
