把一种性别记成 +1、另一种记成 -1，问题就转成最长和为 0 的子数组；记录每个前缀和第一次出现的位置即可。
OJ: luogu
题目 ID: P1114
难度:普及-
标签:前缀和思维枚举
日期: 2026-06-20 11:07
题意
给出 n 个人，已经按身高顺序站好。每个人用：
0表示一种性别1表示另一种性别
现在要选出一段连续的人，使得：
- 这段里
0和1的人数相等
问最多能选出多少人。
思路
先看一个最直接的小数据暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0;
// 朴素枚举所有区间，统计 0 和 1 的数量。
for (int l = 1; l <= n; l++) {
int cnt0 = 0;
int cnt1 = 0;
for (int r = l; r <= n; r++) {
if (a[r] == 0) {
cnt0++;
} else {
cnt1++;
}
if (cnt0 == cnt1) {
ans = max(ans, r - l + 1);
}
}
}
cout << ans << '\n';
return 0;
}brute.cpp 枚举所有区间，统计其中 0 和 1 的个数，只要两者相等就更新答案。
这个做法很好理解，但复杂度是
第一步：把 0/1 转成 -1/+1
题目真正关心的是：
- 两种性别人数相等
所以可以把：
1看成+10看成-1
这样一段区间里如果两种人数相等，那么这段区间的和就恰好是 0。
于是题目转成：
- 求最长的连续子数组，使它的和为
0
第二步：前缀和相同，中间区间和就是 0
设 sum[i] 表示前 i 个人转换后的前缀和。
如果某两个位置满足：
sum[l] = sum[r]
那么区间 (l+1 .. r) 的和就是 0。
因为：
sum[r] - sum[l] = 0
所以只要记录每个前缀和值第一次出现的位置，当它以后再次出现时，就能得到一个男女数量相等的区间。
第三步：为什么只记第一次出现的位置
因为我们要求的是最长区间。
对某个固定前缀和值来说：
- 最早出现的位置越靠前
- 之后再遇到同样的前缀和值时，区间就越长
所以只保留第一次出现的位置即可。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n;
int a[MAXN];
int first_pos[MAXN * 2];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int limit = 2 * n + 2;
for (int i = 0; i <= limit; i++) {
first_pos[i] = -1;
}
int sum = 0;
int offset = n;
int ans = 0;
// 前缀和为 0 在位置 0 先出现一次。
first_pos[offset] = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == 1) {
sum++;
} else {
sum--;
}
int idx = sum + offset;
if (first_pos[idx] == -1) {
first_pos[idx] = i;
} else {
ans = max(ans, i - first_pos[idx]);
}
}
cout << ans << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的核心是把“男女人数相等”转成“区间和为 0”。
一旦想到把两种性别映射成 +1/-1，后面就是标准的：
- 前缀和相同
- 中间区间和为
0
的模型。