[Hall定理] [破环为链] CF981F Round Marriage

· · 题解

显然二分答案，转化为判定性问题。

那么对于验证 k，考虑让新郎 a_i 向所有可以匹配的新娘连边，那么 k 合法，当且仅当建出的二分图有完美匹配。

考虑 \rm Hall 定理，首先将 a,b 排序，尽量让 a_i 管辖的 b 构成一段连续区间。

不过这是环，所以我们需要破环成链。注意一下，假设第 p 份表示将原数组复制然后每一项加 p\times L，那么应该选择第 2,3 份 a 和 1,2,3,4 份 b，才能表示出所有情况。这很重要。

于是现在 a_i 管辖 [L_i,R_i]，贪心地，必然是选择一段连续的 a_i 才能更劣，判定 [i,j] 即为：j-i+1\le R_j-L_i+1，移项得 L_i-i\le R_j-j，扫描一遍即可。

然后有两个细节：

  1. 假如 [L,R] 覆盖的 b 出现重复元素（对应原序列而言）：此时必然已经覆盖了原 b 序列一遍，肯定多于 a 的数量，所以不用考虑。

  2. 假如 a 中 [i,j] 实际覆盖的 b 并不连续，即存在某个 b 不被任何 a 覆盖：那么设其为 b_{pos}，那么必然有一个 a 多出来；反向思考，对于 b_1\dots b_{pos-1} 和 b_{pos+1}\dots b_n，必然存在一者使得对应的 a 数量小于 b 数量，就不满足 \rm Hall 定理了。所以一定非法，无需特判。

有些抽象。

二分查找 L_i,R_i，复杂度 O(n\log n\log V)。双指针代替可做到 O(n\log V)。

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 5, inf = 1e10;
int n, len, a[N], b[N];

inline bool check(int p){
    int mx = -inf;
    for(int i = n + 1; i <= 3 * n; ++i){
        int l = lower_bound(b + 1, b + 1 + 4 * n, a[i] - p) - b, r = upper_bound(b + 1, b + 1 + 4 * n, a[i] + p) - b - 1;
        if(l > r) return false;
        if(mx > r - i) return false;
        mx = max(mx, l - i);
    }
    return true; 
}
signed main(){
    cin >> n >> len;
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    for(int i = 1; i <= n; ++i) scanf("%lld", &b[i]);
    sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + n);
    for(int i = n + 1; i <= 4 * n; ++i) a[i] = a[i - n] + len, b[i] = b[i - n] + len;
    int L = -1, R = 1e9 + 5;
    while(L + 1 < R){
        int mid = L + R >> 1;
        if(check(mid)) R = mid;
        else L = mid; 
    }
    cout << R;
    return 0;
}