【计蒜客题解/洛谷题解】P1114/T1853“非常男女”计划_计蒜客 洛谷

题目概况

计蒜客链接： https://nanti.jisuanke.com/t/T1853
洛谷链接： https://www.luogu.com.cn/problem/P1114
难度： 普及/提高-（计蒜客评级普及T2）

题目分析

简化题目： 求出最长连续的，男女人数相等的序列
涉及知识点： 前缀和
解题思路：
典型的前缀和区间最值问题。利用前缀和思想，我们可以把女生的0直接记为-1。前缀和数组中，哪个区间和为0，就证明从1~i是一段合法序列；但还有起点不是1的，利用 前缀和区间可减性，两个区间和相减为0也是合法的，用一个vis[MAXN]数组标记第一次（可以保证长度递增）出现该前缀和的位置即可。再用ans不断更新答案。

代码要点拆解

相信前缀和预处理环节无须多言，重点讲一下答案更新
1. 如果当前前缀和为0，更新
2. 如果当前前缀和出现过，区间标号相减，更新
3. 如果当前前缀和没有出现，则为第一次出现，记录

    for (int i = 1; i <= n; i++ ){
        if (sum[i] == 0) { //前缀和为0
            ans = max(ans, i);
        } else if (vis[sum[i] + n]) {
            ans = max(ans, i - vis[sum[i] + n]);
        } else {
            vis[sum[i] + n] = i;
        }
    
1
2
3
4
5
6
7
8
9

完整代码

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1e5 + 5;   
int n, ans;
int arr[MAXN], sum[MAXN], vis[MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        if (arr[i] == 0) arr[i] = -1;
        sum[i] = sum[i - 1] + arr[i];
    }
    for (int i = 1; i <= n; i++ ){
        if (sum[i] == 0) {
            ans = max(ans, i);
        } else if (vis[sum[i] + n]) {
            ans = max(ans, i - vis[sum[i] + n]);
        } else {
            vis[sum[i] + n] = i;
        }
    }
    printf("%d", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27