题解：CF1278C Berry Jam

fly_bamboo · 2025-10-30 16:53:08 · 题解

我们考虑枚举我们删哪一段区间。

我们假设所有红果酱和蓝果酱的数量之差为 pos。

那么我们删除的一段区间内，这段区间的红果酱数量和蓝果酱数量之差也要为 pos，才能使两种果酱的差为 0。

那么这就是一个前缀和的问题了。

起点肯定在前面一半内，我们枚举每个点作起点，然后把这个下标存到果酱之差的位置上。

接着在右边一半枚举终点（因为答案可能为 0，所以枚举从 n 开始），看看有没有这个差 -pos 的前缀和，有的话就取这个区间，然后选择最小答案。

代码容易实现（记得清空）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum1[200005],sum2[200005];
int n,a[200005];
map<int,int> vis;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=2*n;i++) cin>>a[i];
        for(int i=1;i<=2*n;i++)
        {
            sum1[i]=sum1[i-1];
            sum2[i]=sum2[i-1];
            sum1[i]+=(a[i]==1);
            sum2[i]+=(a[i]==2);//维护两种果酱的前缀和
        }
        int pos=sum1[2*n]-sum2[2*n];//所有果酱的差
        int minn=1e18;
        vis[0]=0;
        for(int i=1;i<=n;i++)
        {
            vis[sum1[i]-sum2[i]]=max(vis[sum1[i]-sum2[i]],i);//存储，因为答案要最小，所以起点取最大
        }
        for(int i=n;i<=2*n;i++)
        {
            minn=min(minn,i-((sum1[i]-sum2[i]-pos!=0&&vis[sum1[i]-sum2[i]-pos]==0)?(int)-1e18:vis[sum1[i]-sum2[i]-pos]));//取答案，特判0
        }
        vis.clear();//清空
        cout<<minn<<'\n'; 
    }
    return 0;
}