题解：P10435 [JOISC 2024 Day2] 有趣的家庭菜园 5

· · 题解

我们将 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;
}