【CF981F】Round Marriage

题面

https://www.luogu.org/problem/CF981F

题解

二分答案+二分图匹配检验 $ o$ 二分答案+霍尔定理检测。

对于处理环的情况，破环为链，注意如果跑了一圈，会有重复的对答案造成影响，但不会对$check()$函数的正确性产生影响。

2,3 $ o$ 1,2,3,4 以后一定我会记得的。

#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200500
#define LL long long
#define ri register int
using namespace std;

inline int read() {
  int ret=0,f=0; char ch=getchar();
  while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
  while (ch>='0' && ch<='9') ret*=10,ret+=(ch-'0'),ch=getchar();
  return f?-ret:ret;
}

int n,l;
LL a[N<<1],b[N<<2];
int L[N<<1],R[N<<1];

bool check(LL x) {
  int j=1;
  for (ri i=1;i<=2*n;i++) {
    while (b[j]-a[i]<=x && j<=4*n) j++;
    R[i]=j-1;
  }
  j=4*n;
  for (ri i=2*n;i>=1;i--) {
    while (a[i]-b[j]<=x && j>=1) j--;
    L[i]=j+1;
  }
  for (ri i=1;i<2*n;i++) if (L[i+1]-R[i]>=2) return 0;
  deque<int> q;
  while (!q.empty()) q.pop_back();
  for (ri i=1;i<=2*n;i++) {
    while (!q.empty() && L[i]-i>=L[q.front()]-q.front()) q.pop_front(); 
    q.push_front(i);
    while (!q.empty() && i-q.back()>=n) q.pop_back();
    int mx=L[q.back()]-q.back();
    if (R[i]-i-mx<0) return 0;
  }
  return 1;
}

int main() {
  n=read(); l=read();
  for (ri i=1;i<=n;i++) a[i]=read(); 
  sort(a+1,a+n+1);
  for (ri i=1;i<=n;i++) a[i]+=l,a[i+n]=a[i]+l;
  for (ri i=1;i<=n;i++) b[i]=read(); sort(b+1,b+n+1);
  for (ri i=1;i<=3*n;i++) b[i+n]=b[i]+l;
  int ans=l,lb=0,rb=l;
  while (lb<=rb) {
    int mid=(lb+rb)>>1;
    if (check(mid)) ans=mid,rb=mid-1; else lb=mid+1;
  }
  printf("%d
",ans);
  return 0;
}