洛谷P1114 “非常男女”计划

洛谷P1114 “非常男女”计划
map
O(n) 枚举过去
记录当前值最早出现的时间 x ，然后当这个值在时，出现时间为 y 时
则 x+1--y 这段男女出现次数是为一样的，更新一下ans就行了

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <iostream>
 9 using namespace std ; 
10 
11 const int maxn = 100111 ; 
12 int n,sum,x,ans ; 
13 int a[maxn],b[maxn],map[maxn] ; 
14 
15 inline int read() 
16 {
17     char ch = getchar() ; 
18     int x = 0,f = 1 ; 
19     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 
20     while(ch>='0'&&ch<='9') { x = x*10+ch-48 ; ch = getchar() ; }
21     return x * f ; 
22 }
23 
24 int main() 
25 {
26     n = read() ; 
27     for(int i=1;i<=n;i++) 
28     {
29         a[ i ] = read() ; 
30         if(!a[i]) a[i] = -1 ; 
31     }
32     map[ 0 ] = 0 ; 
33     for(int i=1;i<=n;i++ ) 
34     {
35         x+=a[ i ] ;
36         if(!x) ans = max(ans,i) ; 
37         if(map[ x ]) ans = max(ans,i - map[ x ] ) ;  
38         if(!map[ x ]) map[ x ] = i ; 
39     }
40     printf("%d
",ans) ;  
41     return 0 ; 
42 }