取硬币（思维）

Description

n个硬币排成一排，你可以取走其中连续的一段硬币，但必须要求这段硬币中正面朝上的个数等于反面朝上的个数，那么你最多可以取走多少枚硬币？

Input

多组实例测试，每组输入一个01字符串（长度小于1000000），其中0表示反面朝上，1表示正面朝上

Output

对于每组数据，输出能取走的最多硬币数量

Sample Input

Sample Output

Case #1: 4

令t为当前1的个数与0的个数的差，那么遍历字符串，只要这个差值之前出现过，就说明中间这一段0和1的个数一定相等

 1 #include <bits/stdc++.h>
 2 const int INF=0x3f3f3f3f;
 3 typedef long long LL;
 4 const double eps =1e-8;
 5 const int mod=1e9+7;
 6 const int maxn=1e5+10;
 7 using namespace std;
 8 
 9 char str[1000005];
10 map<int,int> mp;
11 
12 int main()
13 {
14     #ifdef DEBUG
15     freopen("sample.txt","r",stdin);
16     #endif
17     
18     int cnt=0;
19     while(~scanf("%s",str+1))
20     {
21         mp.clear();
22         cnt++;
23         int ans=0;
24         int num1=0,num2=0;
25         mp[0]=0;
26         for(int i=1;str[i];i++)
27         {
28             if(str[i]=='1') num1++;
29             else num2++;
30             if(mp.count(num1-num2))
31             {
32                 ans=max(ans,i-mp[num1-num2]);
33             }
34             else mp[num1-num2]=i;
35         }
36         printf("Case #%d: %d
",cnt,ans);
37     }
38     
39     return 0;
40 }