CF1278C

题目大意为给你一个2xN的数列问你从中间开始向左边或者向右边每次移动一个单位吃果酱，最少移动多少次可以吃的使得1号果酱的个数等于2号果酱的个数
首先记录最初的果酱的差值1-2为dif，然后我们发现如果往左边吃一号果酱，那么dif++，吃二号果酱dif–往右边同理。那么我们可以得到最终dif-difl-difr=0也就是说原来的差值减去左边贡献的差值减去右边贡献的差值最后结果为0.这样我们记录一下左边产生的差值在右边遍历寻找左边是否会有dif-difr的然后更新答案。最后注意一下0和只吃左边的情况。

#include <bits/stdc++.h>
using namespace std;
map<int,int> mk;
int a[200005];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,s1=0,s2=0,cur=0,s;
		cin>>n;
		mk.clear();
		for(int i=1;i<=2*n;i++)
		cin>>a[i],s1+=(a[i]==1),s2+=(a[i]==2);
		s=s1-s2;
		mk[0]=0;
		for(int i=n;i;i--)
		{
			if(a[i]==1) cur++;
			else cur--;
			if(!mk.count(cur))
			mk[cur]=n-i+1;
		}
		cur=0;
		int ans=2*n;
		for(int i=n+1;i<=2*n;i++)
		{
			if(a[i]==1) cur++;
			else cur--;
			if(mk.count(s-cur))
			ans=min(ans,i-n+mk[s-cur]); 
		}
		if(mk.count(s))
		ans=min(ans,mk[s]);
		cout<<ans<<"\n";
	}
}