【CF981F】Round Marriage（二分答案，二分图匹配，Hall定理）
题面
题解
很明显需要二分。
二分之后考虑如果判定是否存在完备匹配，考虑\(Hall\)定理。
那么如果不合法，假设我们存在一个极小的集合满足连到右侧的点数小于集合大小。因为是极小的，所以删去一个点之后就可以匹配，那么意为着某个点连出去的点和其他所有点有交，既然有交，那么一定这一段区间都可以加入进来形成一个不合法的集合。所以我们可以把存在一个点集不合法变成存在一段连续区间不合法。
假设每个点连向另外一侧的区间是\([L_l,R_i]\)，那么如果区间\([l,r]\)不满足\(Hall\)定理，那么可以得到\(r-l>R_r-L_l\)，移项之后可以得到\(r-R_r>l-L_l\)，然后随便维护一下就行了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 800800
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,L;ll a[MAX],b[MAX];
bool check(int len)
{
int mx=-1e9,p1=1,p2=1;
for(int i=1;i<=n+n;++i)
{
while(p1<=n+n+n+n&&b[p1]<a[i]-len)++p1;
while(p2<=n+n+n+n&&b[p2]<=a[i]+len)++p2;
mx=max(mx,p1-i);
if(p2-i-1<mx)return false;
}
return true;
}
int main()
{
n=read();L=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)b[i]=read();
sort(&a[1],&a[n+1]);sort(&b[1],&b[n+1]);
for(int i=1;i<=n;++i)a[i]+=L,a[i+n]=a[i]+L;
for(int i=1;i<=n+n+n;++i)b[i+n]=b[i]+L;
int l=0,r=L,ret=L;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))r=mid-1,ret=mid;
else l=mid+1;
}
printf("%d\n",ret);
return 0;
}