CF981F

CF981F

有 \(n\) 个男生和 \(n\) 个女生围成一个环，第 \(i\) 个男生的位置为 \(a_i\)，女生为 \(b_i\)，这个环的大小为 \(L\)，坐标为 \(0,1,2...L\)

将这 \(n\) 对人配对，使得距离最大的对子最小。

\(n\le 2\cdot 10^5,L\le 10^9\)

Solution

二分答案，怎么 check。

我们等价于求完美匹配，根据 Hall 定理，等价于只考虑男生的每个子集，均有配对的女生数量大于男生数量。

设点 \(i\) 可以配对的女生编号为 \(L_i\to R_i(\mod n)\)，那么对于任意子集均有合法。

我们发现假设这个子集不连续，那么其限制一定没有连续的一段区间作为子集对答案的限制更严。

所以考虑两个端点 \(i,j\)，区间 \([i,j]\) 合法我们怎么检查，一定可以让 \(i\) 匹配上 \(L_i\) 女生，\(j\) 匹配 \(R_j\) 女生，这样就变成 \([i+1,j-1]\) 的问题了。

能够这样操作的前提是这个区间对应的女生人数大于男生，不难发现这是一个必要条件，同时可以推出其为充分条件。

于是合法的条件即 \(R_j-L_i\ge j-i\) 即 \(R_j-j\ge L_i-i\)

然而如果这个题是序列那么就做完了，问题在于这个题是要求环。

那么可以基于这样的考虑：

• 假设区间 \([i,j]\) 满足 \(i\) 往左匹配点和 \(j\) 往右匹配点相交了，那么区间 \([i,j]\) 一定是合法的，因为他们对应的女生数是 \(n\)

所以我们只需要检查不满足这个条件的区间，于是只需要检查正序的区间和逆序的区间，这样将 \(a,b\) 倍长 \(4\) 倍，然后选中间部分的区间进行检查即可，使用双指针扫两边即可。

复杂度 \(\mathcal O(n\log w)\)

\(Code:\)

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < ‘0‘ || cc > ‘9‘ ) {  if( cc == ‘-‘ ) flus = - flus ; cc = getchar() ; }
	while( cc >= ‘0‘ && cc <= ‘9‘ )  cn = cn * 10 + cc - ‘0‘, cc = getchar() ;
	return cn * flus ;
}
const int N = 1e6 + 5 ; 
int n, m, a[N], b[N], ll[N], rr[N] ; 
bool check(int x) {
	int l = 1, r = 4 * n ; 
	for(re int i = n + 1; i <= 3 * n; ++ i) {
		while( a[l] < b[i] - x ) ++ l ;
		ll[i] = l - i ; 
	}
	for(re int i = 3 * n; i >= n + 1; -- i) {
		while( a[r] > b[i] + x ) -- r ; 
		rr[i] = r - i ; 
	}
	for(re int i = n + 2; i <= 3 * n; ++ i) ll[i] = max(ll[i - 1], ll[i]) ; 
	for(re int i = n + 1; i <= 3 * n; ++ i) if(rr[i] < ll[i]) return 0 ; 
	return 1 ; 
}
signed main()
{
	n = gi(), m = gi() ; 
	rep( i, 1, n ) a[i] = gi() ;
	rep( i, 1, n ) b[i] = gi() ; 
	sort(a + 1, a + n + 1), sort(b + 1, b + n + 1) ;
	rep( i, 1, n ) 
		a[i + n] = a[i] + m, a[i + 2 * n] = a[i] + 2 * m, a[i + 3 * n] = a[i] + 3 * m,
		b[i + n] = b[i] + m, b[i + 2 * n] = b[i] + 2 * m, b[i + 3 * n] = b[i] + 3 * m;
	int l = 0, r = m, ans = 0 ;
	while( l <= r ) {
		int mid = (l + r) >> 1 ; 
		if( check(mid) ) ans = mid, r = mid - 1 ;
		else l = mid + 1 ; 
	}
	cout << ans << endl ; 
	return 0 ;
}

CF981F

原文：https://www.cnblogs.com/Soulist/p/13772856.html