自动搬运

查看原文

来自洛谷，原作者为

	min_inf 你路过的 与我追逐的 我会等它们重合

搬运于2025-08-24 23:16:23，当前版本为作者最后更新于2025-05-22 19:20:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

如果 $y=0$ 那显然是排好序之后相邻的匹配，$y\le 1$ 显然也不能有在横坐标上有交的对，且答案最多比不考虑纵坐标的答案多 $1$。我们只要检查能否通过重排每个横坐标内部的顺序得到 $y=0$ 时的答案 $lim$。

首先判掉每个横坐标内部都可以全部匹配的情况。考虑 DP，设 $f_{i,0/1}$ 表示考虑第 $i$ 小的横坐标，最后一个元素是 $0/1$ 是否可行。如果 $i$ 前面总共有偶数个元素或者 $i$ 到前面的距离小于 $lim$，就是可以随便排；否则就是对第一个元素的 $y$ 有要求，注意一下只有一个元素的情况。

时间复杂度 $O(n\log n)$，瓶颈在排序。

cin>>n;rep(i,1,n*2)cin>>a[i].fir>>a[i].sec;
sort(a+1,a+2*n+1);
bool z=1;rep(i,1,n)z&=a[2*i-1]==a[2*i];
if(z){cout<<"0\n";return 0;}
ll mx=0;rep(i,1,n)mx=max(mx,a[2*i].fir-a[2*i-1].fir);
if(!mx){cout<<"1\n";return 0;}
bool o0=1,o1=1,s=0;rep(i,1,2*n){
    int j=i;while(j<2*n&&a[j+1].fir==a[i].fir)++j;
    int c1=0;rep(k,i,j)c1+=a[k].sec;int c0=j-i+1-c1;
    bool n0=0,n1=0;
    if(!s||a[i].fir-a[i-1].fir<mx){
        if(o0||o1)n0=c0,n1=c1;
    }else{
        if(o0&&c0)n0|=c0>1||!c1,n1|=c1;
        if(o1&&c1)n0|=c0,n1|=c1>1||!c0;
    }
    s^=j-i+1&1,i=j,o0=n0,o1=n1;
}
if(!o0&&!o1)++mx;cout<<mx<<'\n';