mengbierr

一个蒟蒻的博客

6月15

Codeforces 981F. Round Marriage

题意

n 个新郎和 n 个新娘围成一个环,长度为 L ,第 i 个新郎位置为 a_i ,第 i 个新娘位置为 b_i ,需要将他们两两配对,最小化新郎和新娘距离的最大值。

题解

显然要二分答案…
i 个新郎和第 j 个新娘距离为 min(|a_i-b_j|,L-|a_i-b_j|),将每个新娘复制三次,坐标分别为 b_j ,b_j-L,b_j+L,这样就能方便的计算每个新娘与新郎的距离,而且只会有一个点在合法范围内,这样two pointer一下一定是选两边就行了…

发表评论

电子邮件地址不会被公开。 必填项已用*标注