B. Balanced Substring
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given astring s consisting only of characters 0 and 1. A substring [l,?r] of s is astring slsl?+?1sl?+?2... sr, and its lengthequals to r?-?l?+?1. A substring iscalled balanced if the number of zeroes (0) equals to the number of ones in thissubstring.
You have todetermine the length of the longest balanced substring of s.
Input
The first linecontains n (1?≤?n?≤?100000) — the numberof characters in s.
The second linecontains a string s consisting of exactly n characters.Only characters 0 and 1 can appearin s.
Output
If there is nonon-empty balanced substring in s, print 0. Otherwise, print the length of thelongest balanced substring.
Examples
input
Copy
8
11010111
output
Copy
4
input
Copy
3
111
output
Copy
0
Note
In the firstexample you can choose the substring [3,?6]. It is balanced, and itslength is 4. Choosing the substring [2,?5] is also possible.
In the secondexample it's impossible to find a non-empty balanced substring.
算法分析：
题意：
题意难以理解，就是求在一段长度中，1和0的个数相同，求最大长度。
分析：
我们把0看作-1，两种情况便出现上述形式。
1.i之前数字和为0（前缀和）
2.i+n的前缀和与i的前缀和相同
所以需要一个数组记录每一个i的前缀和，因为可能有负数，所以这里用到map（map类点这里）
代码实现：
#include <iostream>
#include <string>
#include <map>
using namespace std;
int s[100001];
int main()
{int n;string a;cin>>n;cin>>a;map<int,int>q;//可能为负数，所以用map，记录i的前缀和 int sum = 0,maxi = 0;for(int i=0;i<n;i++){if(a[i]=='0')sum+=-1;else sum += 1;if(!q[sum]&&sum)q[sum]=i+1;//如果sum为0表示本来就平衡不需要标记了//并记录i+1的前缀和else {maxi=max(maxi,i-q[sum]+1); //存在前缀和相同的，满足平衡树}}cout<<maxi<<endl;
}