专栏文章

题解：CF1278C Berry Jam

ffly_bamboo
CF1278C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingci68
此快照首次捕获于
2025/12/02 01:57
3 个月前
此快照最后确认于
2025/12/02 01:57
3 个月前
查看原文
我们考虑枚举我们删哪一段区间。
我们假设所有红果酱和蓝果酱的数量之差为 pospos。
那么我们删除的一段区间内，这段区间的红果酱数量和蓝果酱数量之差也要为 pospos，才能使两种果酱的差为 00。
那么这就是一个前缀和的问题了。
起点肯定在前面一半内，我们枚举每个点作起点，然后把这个下标存到果酱之差的位置上。
接着在右边一半枚举终点（因为答案可能为 00，所以枚举从 nn 开始），看看有没有这个差 −pos-pos 的前缀和，有的话就取这个区间，然后选择最小答案。
代码容易实现（记得清空）：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...