自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:57:56，当前版本为作者最后更新于2024-09-17 11:58:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们将 $2N$ 个花盆顺时针排成一个环，题目的要求就是 $2$ 种颜色的花盆各是一个半圆。

考虑如果已经确定了花盆颜色，怎么安排最优。

那么问题就是，给定 $2$ 个长度为 $n$ 的序列 $a,b$，要求两两配对，使得配对的 $2$ 个数的差值最大值最小。

可以发现，将 $a,b$ 排序后，从小到大依次配对一定是最优的。

证明考虑，假如我们已经知道了最优答案为 $k$，要求一组配对方案。

那么这相当于一个二分图匹配问题，注意到排序后每个 $a$ 可以匹配的都是 $b$ 的一段区间，并且这些区间的左右端点都是单调递增的，因此从小到大依次匹配是最优的。

上述证明过程启示我们考虑二分答案，判断是否存在可行解。

注意到 $B$ 和 $C$ 是等价判定，所以我们相当于要判断 $2N$ 个半圆中，每个半圆是否可行。

枚举半圆似乎并不好解决，我们考虑枚举圆环上的点，判断经过每个点的 $N$ 个半圆中哪些是可行的。

首先用双指针求出每个 $A_i$ 在 $B$ 上可以匹配的区间 $[l_i,r_i]$，那么根据上述匹配方式，半圆可行当且仅当半圆中小于等于 $A_i$ 的数的个数在 $l_i$ 和 $r_i$ 之间，注意这里我们要将 $A$ 中相等的数钦定大小关系。

然后题目还保证了一个关键性质，那就是 $A$ 是一个前一半增后一半减的序列。

那么我们按照顺时针的顺序考虑经过一个 $A_i$ 的所有半圆中小等 $A_i$ 的数的个数，通过一些推导或者打表观察可以发现，把其写为函数的形式，一定是一段水平线段和一段 $45$ 度的斜线段拼接在一起的形式，那么合法的半圆的也是圆环上的一段区间。

那么我们用差分的方式对一段区间的半圆做标记，可行的半圆就是被所有点都标记的半圆。

上述过程都可以在线性的复杂度内解决，加上二分的复杂度，时间复杂度 $O(n\log V)$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
int n,m,a[N],b[N],c[N],lim,ans[N],Ans[N],vl[N],vr[N],p1[N],p2[N];
void upd(int o,int l,int r){
	l=(l+o)%m,r=(r+o)%m;
	if(l>r)++ans[0],--ans[r+1],++ans[l];
	else ++ans[l],--ans[r+1];
}
void solve(int *v){
	for(int i=0,j=1;i<n;++i){
		while(j<=n&&v[j]<a[i]&&a[i]-v[j]>lim)++j;
		vl[i]=j;
	}
	for(int i=n-1,j=n;~i;--i){
		while(j&&v[j]>a[i]&&v[j]-a[i]>lim)--j;
		vr[i]=j;
	}
	for(int i=m-1,j=1;i>=n;--i){
		while(j<=n&&v[j]<a[i]&&a[i]-v[j]>lim)++j;
		vl[i]=j;
	}
	for(int i=n,j=n;i<m;++i){
		while(j&&v[j]>a[i]&&v[j]-a[i]>lim)--j;
		vr[i]=j;
	}
	for(int i=0;i<m;++i)ans[i]=0;
	for(int i=0;i<n;++i)if(vl[i]<=vr[i]){
		int ct=i+1+m-max(p1[i],i+n+1);
		if(ct<vl[i])continue;
		if(p1[i]>=i+n+1){
			int dt=p1[i]-(i+n+1);
			if(ct-(n-dt)>vr[i])continue;
			if(ct<=vr[i])upd(i+n+1,0,min(n-1,dt+ct-vl[i]));
			else upd(i+n+1,dt+ct-vr[i],min(n-1,dt+ct-vl[i]));
		}else{
			int dt=i+n+1-p1[i];
			if(ct-(n-dt)>vr[i])continue;
			if(ct-(n-dt)>=vl[i])upd(i+n+1,max(0,ct-vr[i]),n-1);
			else upd(i+n+1,max(0,ct-vr[i]),ct-vl[i]);
		}
	}
	for(int i=n;i<m;++i)if(vl[i]<=vr[i]){
		int ct=1+max(0,p2[i]-(i-n));
		if(ct>vr[i])continue;
		if(p2[i]>=i-n){
			int dt=p2[i]-(i-n);
			if(ct+(n-dt)<vl[i])continue;
			if(ct>=vl[i])upd(i-n+1,0,min(n-1,dt+vr[i]-ct));
			else upd(i-n+1,dt+vl[i]-ct,min(n-1,dt+vr[i]-ct));
		}else{
			int dt=i-n-p2[i];
			if(ct+(n-dt)<vl[i])continue;
			if(ct+(n-dt)<=vr[i])upd(i-n+1,max(0,vl[i]-ct),n-1);
			else upd(i-n+1,max(0,vl[i]-ct),vr[i]-ct);
		}
	}
	for(int i=1;i<m;++i)ans[i]+=ans[i-1];
}
bool check(int mid){
	lim=mid;
	solve(b);
	for(int i=0;i<m;++i)Ans[i]=ans[i];
	solve(c);
	for(int i=0;i<m;++i)if(Ans[i]+ans[(i+n)%m]==m)return true;
	return false;
}
int main(){
	scanf("%d",&n);
	m=2*n;
	for(int i=0;i<m;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)scanf("%d",&b[i]);
	for(int i=1;i<=n;++i)scanf("%d",&c[i]);
	for(int i=0,j=m-1;i<n;++i){
		while(a[j]<a[i])p2[j--]=i-1;
		p1[i]=j+1;
		if(i==n-1)while(j>=n)p2[j--]=i;
	}
	sort(b+1,b+n+1),sort(c+1,c+n+1);
	int l=0,r=1e9;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}