题解 P1114 【“非常男女”计划】

北文 · 2019-11-13 18:46:04 · 题解

和楼下思路基本一样，相对差。

统计第一个出现的位置，以后每找到一个与他相等的，就更新最大

值， （代码特骚）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k=0, x, l[100006] /*统计第一个出现的位置 */, ans=0;
    scanf("%d", &n);
    memset(l, -1, sizeof(l));//初始化为-1
    l[0]=0;//重点，在第0个（即没有人）为相等
    for(int i=1; i<=n; i++) {
        scanf("%d", &x);
        if(x==1)k+=1;//男生+1
        else k-=1;//女生-1
        if(l[k]==-1)l[k]=i;//若没有就存储
        else ans=max(ans,i-l[k]);//更新ans
    }
    printf("%d", ans);
    return 0;
}