Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

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

posted on 2021-07-19 17:09:08 | under 贪心 |

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

代码