题解：CF981F Round Marriage

· · 题解

什么是 Hall 定理，蒟蒻不知道。

考虑二分答案，问题转化为是否能在 mid 距离内为每个少男找到匹配的少女。

首先证明对于一个两个位置序列，最优匹配方案一定是分别从小到大排序后依次匹配。分类讨论即可。

然后证明对于环上问题，最优匹配方案一定不同时存在有少男从左端到右端和从右端到左端的情况。并且一定是一段前缀或后缀的少男匹配到环的另一端。

这样我们就有了断环为链的前提，并且知道了匹配方式。把少女的位置序列 b 复制三份，分别存 L-b_i、b_i 和 L+b_i，首尾相接设为 B。最优方案就是其中连续长度为 n 的某一段和 a_i 进行的如上所述的匹配。

这样写还是会TLE，考虑优化。发现可与 a_i 匹配的位置在 B 上是一段区间，并且左右端点随i增大单调递增，可 O(n) 求出。并且发现若 1 \sim i-1 的 a 符合匹配条件的 B 的右端点的取值为 [L,R] ，那么相当于 a_i 可以“接上”的范围为 [L+1,R+1]，又要符合自己的匹配条件，取交集即可。

时间复杂度 O(n \log V)。

#include <bits/stdc++.h>
using namespace std;

int n, LL, a[200002], b[600002];
int have[200002];
bool check(int s){
    int l = 1, r = 1, nowl = 1, nowr = 3 * n;
    for(int i=1;i<=n;i++){
        while(l <= 3 * n && b[l] < a[i] - s) l++;
        while(r <= 3 * n && b[r] <= a[i] + s) r++;
        r--;
        nowl = max(nowl, l), nowr = min(nowr, r);
        nowl++, nowr++;
    }
    return nowl <= nowr;
}

int main(){
    //freopen("marriage1.in","r",stdin);

    scanf("%d%d",&n,&LL);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=n+1;i<=2*n;i++) scanf("%d",&b[i]);
    sort(a+1,a+n+1), sort(b+n+1,b+2*n+1);
    for(int i=1;i<=n;i++) b[i] = b[n+i] - LL;
    for(int i=n*2+1;i<=n*3;i++) b[i] = b[i-n] + LL;

    int l = 0, r = 2e9;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d",l);

    return 0;
}