【CF 873B】Balanced Substring

一个01串中如果包含有1和0的数目相等的子串，则称之为“平衡”，找出该字符串中最长的平衡串；

思路：先对字符串进行处理，1的值为1,0的值为-1，存入数组。然后求取前n项之和，如果有两个字符串前n项和相同,说明这两个字符串之间的值总和为0，求出最长序列即可。

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
using namespace std;

int a[100005];
map<int,int>mp;
int main()
{
	int n,i;
	string s;
	cin>>n;
	cin>>s;
	for(i=1;i<=n;i++)
	{
		if(s[i-1]=='0')                //由于mp[tmp]初始值为0，因此取得正确的max，i的下标应从1开始；
		a[i]=-1;
		else
		a[i]=1;
	}
	mp.clear();
	int tmp=0,max=0;
	for(i=1;i<=n;i++)
	{
		tmp+=a[i];
		if(tmp!=0&&!mp[tmp])
		{
			mp[tmp]=i;
			//cout<<mp[tmp]<<" "<<tmp<<endl;
		}
		else
		{
			if(i-mp[tmp]>max)
				max=i-mp[tmp];            
			//cout<<i<<" "<<mp[tmp]<<endl;
		}
	}
	cout<<max<<endl;
	return 0;
}