题解：CF981F Round Marriage

· · 题解

题解区里二分 + Hall 定理的判断方法，并没有保证区间长度 \le L。这里补一个证明。

首先，新郎 \le L，新娘 \gt L，这个对答案是没有贡献的。

考虑新郎 \gt L，新娘 \gt L。

如图。上面的线是新郎，下面的是新娘。 a,b 是对应区间新郎的数量。c,d 同理。 中间的是跨域的部分，长为 L，各有 n 个人。

因为正确性在于若 a+n+b\gt c+n+f，不满足 Hall 定理，导致错误。

若 a+n+b\gt c+n+f，所以 a+b\gt c+f。把左边的 a,c 等价于右边的 a,c。 所以 \ge L 的判定必定存在一个总长度 \lt L 的等价判定。

证毕。