2023年广东工业大学腾讯杯新生程序设计竞赛不知道叫什么名字(前缀和)

需要的是男生女生数量相同，做个转化，女生变成-1，然后求一遍前缀和，我们希望找到最长的满足\(sum(l, r)=0\)的区间也就是\(sum(r) - s(l - 1) = 0\)
考虑枚举右端点，找到最左端和它相等的sum就是对于当前右端点的最长的。

最开始想了个二分答案的假做法，011100，这里答案是6，长度为4不满足

#include <bits/stdc++.h> 
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define db double
#define ull unsigned long long
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5 + 10;
int t, n;
int a[N], sum[N], b[N], ans;
map<int, int>mp;

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; ++ i)
	{
		cin >> a[i];
		if(a[i] == 0)	a[i] = -1;
		sum[i] = sum[i - 1] + a[i];
	}
	for(int i = n; i >= 1; -- i)	mp[sum[i]] = i;
    mp[0] = 0;
	for(int i = 1; i <= n; ++ i)	ans = max(ans, i - mp[sum[i]]);
	cout << ans << endl;
}

int main()
{
	io
//	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
	solve(); 
	return 0;
}