CF981F Round Marriage

传送门

首先最小化最大，一眼鉴定为二分。二分这个最大值 \(k\)，问题变成判断是否能让新郎新娘匹配，每一对距离 \(\le k\)。

如果把新郎新娘视作二分图，每个点只和距离 \(\le k\) 的点连边，问题就是求是否有完美匹配。

完美匹配判定，可以联想到 Hall's 定理。

先把环复制一遍，然后在链上处理。
可以 \(O(n)\) 预处理出他向左、向右最远能到达哪个新娘。易知每个新郎能访问到的新娘必然是一个区间。

感性理解，要尽可能取一个新郎集合违背 Hall's 定理，一定是取一个新郎区间最好。所以只需要判断是否有一个新郎区间对应的新娘数量少于新郎。

双指针即可。