专栏文章

题解：CF981F Round Marriage

DDanslapiscine
CF981F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq9jd9a
此快照首次捕获于
2025/12/04 01:10
3 个月前
此快照最后确认于
2025/12/04 01:10
3 个月前
查看原文
什么是 Hall 定理，蒟蒻不知道。
考虑二分答案，问题转化为是否能在 midmid 距离内为每个少男找到匹配的少女。
首先证明对于一个两个位置序列，最优匹配方案一定是分别从小到大排序后依次匹配。分类讨论即可。
然后证明对于环上问题，最优匹配方案一定不同时存在有少男从左端到右端和从右端到左端的情况。并且一定是一段前缀或后缀的少男匹配到环的另一端。
这样我们就有了断环为链的前提，并且知道了匹配方式。把少女的位置序列 bb 复制三份，分别存 L−biL-b_i、bib_i 和 L+biL+b_i，首尾相接设为 BB。最优方案就是其中连续长度为 nn 的某一段和 aia_i 进行的如上所述的匹配。
这样写还是会TLE，考虑优化。发现可与 aia_i 匹配的位置在 BB 上是一段区间，并且左右端点随i增大单调递增，可 O(n)O(n) 求出。并且发现若 1∼i−11 \sim i-1 的 aa 符合匹配条件的 BB 的右端点的取值为 [L,R][L,R] ，那么相当于 aia_i 可以“接上”的范围为 [L+1,R+1][L+1,R+1]，又要符合自己的匹配条件，取交集即可。
时间复杂度 O(nlog⁡V)O(n \log V)。
CPP
#include <bits/stdc++.h>
using namespace std;

int n, LL, a[200002], b[600002];
int have[200002];
bool check(int s){
	int l = 1, r = 1, nowl = 1, nowr = 3 * n;
	for(int i=1;i<=n;i++){
		while(l <= 3 * n && b[l] < a[i] - s) l++;
		while(r <= 3 * n && b[r] <= a[i] + s) r++;
		r--;
		nowl = max(nowl, l), nowr = min(nowr, r);
		nowl++, nowr++;
	}
	return nowl <= nowr;
}

int main(){
	//freopen("marriage1.in","r",stdin);
	
	scanf("%d%d",&n,&LL);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=n+1;i<=2*n;i++) scanf("%d",&b[i]);
	sort(a+1,a+n+1), sort(b+n+1,b+2*n+1);
	for(int i=1;i<=n;i++) b[i] = b[n+i] - LL;
	for(int i=n*2+1;i<=n*3;i++) b[i] = b[i-n] + LL;
	
	int l = 0, r = 2e9;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	
	printf("%d",l);
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...