【CF981F】Round Marriage(二分答案,二分图匹配,Hall定理)
2024-10-09 19:54:02
【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;
}
最新文章
- nodejs最新教程
- VBA好的插件
- 【Android开发学习笔记】【第十课】运动事件 之——触摸屏
- Calendar的add()方法介绍
- [Tommas] 一种有效的测试策略(转)
- [React] React Router: hashHistory vs browserHistory
- Source insight添加工具自动排版
- FileUtils.copyDirectory without .SVN
- Android官方架构组件介绍之LifeCycle
- java 数据格式验证类
- 判断 Python 版本
- mybatis:访问静态变量或方法
- [nginx] 从源码编译安装NGINX
- openssl实现双向认证教程(服务端代码+客户端代码+证书生成)
- Java并发编程:Java Thread 的 sleep() 和 wait() 的区别
- 53.纯 CSS 创作一个文本淡入淡出的 loader 动画
- 火兰hillstone与fortigate之ipsec v.p.n连接实践
- tmux使用及配置
- Leetcode 96
- 《Spark MLlib 机器学习实战》1——读后总结