题解：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)

，瓶颈在排序。

CPP

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

题解：P12548 [UOI 2025] Manhattan Pairing

文章操作

相关推荐

评论

题解：P12548 [UOI 2025] Manhattan Pairing