【CF981F】Round Marriage（二分答案，二分图匹配，Hall定理）

时间：2022-09-27 07:45:48

【CF981F】Round Marriage（二分答案，二分图匹配，Hall定理）

题面

CF

洛谷

题解

很明显需要二分。

二分之后考虑如果判定是否存在完备匹配，考虑\(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;

}

相关文章