题解：P12548 [UOI 2025] Manhattan Pairing

· · 题解

如果 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';