Codeforces 981F. Round Marriage

Description

一个长度为 \(L\) 的环上有 \(n\) 个黑点和 \(n\) 个白点 , 你需要把黑点和白点配对 , 使得配对点的最大距离最小 , 最小距离定义为两点在环上的两条路径的最小值.

题面

Solution

二分一个答案 , 把距离小于答案的连边 , 现在要判断是否存在完美匹配.

运用 \(Hall\) 定理 , 这题对于所有区间满足 \(Hall\) 定理 , 就满足 \(Hall\) 定理.

对于一段白点区间 \([l,r]\) 我们设他们能匹配到的黑点对应的区间是 \([L,R]\) , \(r-l>R-L\) 就不满足条件.

问题在于本题是个环 , 所以破环成链 , 如何考虑最短路径 ? 只需要把链倍长两次 , 然后从 \(n+1\) 开始考虑 , 这样的话同一个黑点既可以在左边也可以在右边被匹配到了.

#include<bits/stdc++.h>

using namespace std;

template<class T>void gi(T &x){

	int f;char c;

	for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

	for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;

}

typedef long long ll;

const int N=8e5+10;

int n,m,p[N];ll a[N],b[N],q[N],L;

inline bool check(int mid){

	int l=0,r=n,L=1,R=0;

	for(int i=1;i<=n*3;i++){

		while(l<m && b[l+1]<a[i]-mid)l++;

		while(r<m && b[r+1]<=a[i]+mid)r++;

		while(L<=R && i-l-1<=q[R])R--;

		q[++R]=i-l-1,p[R]=i;

		while(L<=R && i-p[L]>=n)L++;

		if(L<=R && i-r>q[L])return false;

	}

	return true;

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  cin>>n>>L;m=n*4;

  for(int i=1;i<=n;i++)gi(a[i]);

  for(int i=1;i<=n;i++)gi(b[i]);

  sort(a+1,a+n+1),sort(b+1,b+n+1);

  for(int i=1;i<=n;i++)

	  for(int j=1;j<=3;j++)a[i+j*n]=a[i]+L*j,b[i+j*n]=b[i]+L*j;

  int l=0,r=L,mid,ans=0;

  while(l<=r){

	  mid=(l+r)>>1;

	  if(check(mid))ans=mid,r=mid-1;

	  else l=mid+1;

  }

  cout<<ans;

  return 0;

}