题解「JOI 2020 Final」只不过是长的领带

Description

「JOI 2020 Final」只不过是长的领带

Analysis

看到最小化最小值,很自然地便会想到二分。

假设为求 \(C_k\),我们二分出一个 \(t\),需判断它是否符合题目要求。

形式化地,我们需验证其是否满足存在一个排列 \(p\),使得对于任意\(i\),有\(A_{p_i}-B_i\le t,p_i\ne k\)。

一种简单的想法是将每个 \(B_i\) 和 \(A_i\) 看成点,并将满足\(A_{p_i}-B_i\le t\) 的点连边,从而转化为求二分图最大匹配的问题。

然而这样下来,本题的复杂度将变为 \(O(n^4\log n)\),只能得到 10 分的成绩。

进而我们想到贪心,即将 \(A\) 和 \(B\) 从小到大排序,小的和小的配对,大的和大的配对,不难通过数学归纳法证明其正确性。

设排序后的数组分别为 \(A',B'\),我们需二分出一个最小的 \(t\),使得对于任意 \(i\),有 \(A'_i-B'_i\le t\)。

显然 \(t\) 就是 \(\max\{A_i-B_i\}\)。

那么我们就得到了本题的解法,将 \(A,B\) 从小到大排序,记录 \(A_i-B_i\) 的前缀 max 和 \(A_{i+1}-B_i\) 的后缀 max,每次查询一下即可。

FBI Warning

注意输出答案的顺序!

Code

代码

上一篇:JOI 地牢题解


下一篇:后端数据验证模块Joi