/*
二分答案，判mid是否合法
如何判断：如果是在直线上，那么遍历匹配即可
现在在环上，即既可以向前匹配也可以向后匹配，那么将环拆开，扩展成三倍
显然a和b的匹配边是不可能交叉的，因为交叉必定没有不交叉优
hall定理：二分图两个点集A,B，连续一段A的点对应连续一段B的点的 充要条件是 这些点对的匹配边之间不交叉
重要推论：二部图G中的两部分顶点组成的集合分别为X,Y, 若|X|=|Y|,
且G中有一组无公共端点的边，一端恰好组成X中的点，一端恰好组成Y中的点，则称二部图G中存在完美匹配
有了这个定理，就可以用在判定上：a的点集对应b点集的连续一段，即b的n个点也是连续的，因为之前已经确定匹配边不交叉
先求出a[1]的范围[a[1]-mid,a[1]+mid]对应的能控制的b数组的范围[l1,r1]
那么a[2]的控制范围要和[l1+1,r1+1]交叉得到[l2,r2]
那么a[3]的控制范围要和[l2+1,r2+1]交叉得到[l3,r3]
...依次类推 可以这个区间长度只会减小不会变大
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
long long n,L,a[maxn],b[maxn<<
2],c[maxn],m;
int judge(
int mid){
//a[i]的控制区间是[a[i]-mid,a[i]+mid]
int l=
1,r=
m;
for(
int i=
1;i<=n;i++
){
while(a[i]-mid>
b[l])
++
l;
while(a[i]+mid<
b[r])
--
r;
if(l>r)
return 0;
++l,++
r;
}
return 1;
}
int main(){
cin>>n>>
L;
for(
int i=
1;i<=n;i++)cin>>
a[i];
for(
int i=
1;i<=n;i++)cin>>
c[i];
sort(c+
1,c+
1+n);sort(a+
1,a+
1+
n);
for(
int i=
1;i<=n;i++)b[i]=c[i]-
L;
for(
int i=
1;i<=n;i++)b[i+n]=
c[i];
for(
int i=
1;i<=n;i++)b[i+
2*n]=c[i]+
L;
m=
3*
n;
int l=
0,r=
L,ans,mid;
while(l<=
r){
mid=l+r>>
1;
if(judge(mid))
ans=mid,r=mid-
1;
else l=mid+
1;
}
cout<<ans<<
'\n';
}
转载于:https://www.cnblogs.com/zsben991126/p/11176246.html
相关资源：各显卡算力对照表！
