Berry Jam（前缀后->差值）

思路：

• 要相等，就一定会减去他们的总的差值，
• 前/后 缀后来处理 左右2边差值的权值。
• 最后更新答案即可。

题目：

SWJTU—春季集训 - Virtual Judge (vjudge.net)

#include 
using namespace std;
#define ri register int
#define M 200005

template <class G> void read(G &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}

int n,m;
int a[M],b[M];
int aa,bb;
int p[M];
int T;
int main(){
    
    read(T);
    while(T--)
    {
        read(n);aa=0,bb=0;
        
    for(ri i=1;i<=2*n;i++)
    {
        read(p[i]);
        if(p[i]==1)
        {
            aa++;
        }
        else bb++;
    }
    if(aa==bb)
    {
        printf("0\n");
        continue;
    }
    int tmp=0;
    for(ri i=n;i>=1;i--)
    {
        if(aa>bb)
        {
            if(p[i]==1)
            {
             tmp++;
             if(tmp>0&&!a[tmp]) a[tmp]=n-i+1;
            }
            else
            {
                tmp--;
            }
        }
        else
        {
            if(p[i]==2)
            {
             tmp++;
             if(tmp>0&&!a[tmp]) a[tmp]=n-i+1;
            }
            else
            {
                tmp--;
            }
        }
    }
    tmp=0;
    for(ri i=n+1;i<=2*n;i++)
    {
        if(aa>bb)
        {
            if(p[i]==1)
            {
             tmp++;
             if(tmp>0&&!b[tmp]) b[tmp]=i-n;
            }
            else
            {
                tmp--;
            }
        }
        else
        {
            if(p[i]==2)
            {
             tmp++;
             if(tmp>0&&!b[tmp]) b[tmp]=i-n;
            }
            else
            {
                tmp--;
            }
        }
    }
    
    int ans=1e9;
    for(ri i=0;i<=abs(aa-bb);i++)
    {
        int j=abs(aa-bb)-i;
        if(a[i]==0&&i!=0) continue;
        if(b[j]==0&&j!=0) continue;
        ans=min(ans,a[i]+b[j]);
    }
    printf("%d\n",ans);
    for(ri i=0;i<=n;i++) a[i]=b[i]=0;
    }
    
    
    
    
    
    
}