一开始思路就想偏了……
# 题面
> Link LOJ #2740
(LOJ 的翻译很清晰了,就不简化了 懒)
# 解析
首先,我们可以考虑只修改 5h 时的榜单中的省份信息。因为所有 2h 和 5h 的选手信息配对完毕后,我们只需要修改 2h 和 5h 的省份信息中的一个。
不妨考虑修改 5h 是的榜单中的省份。那么对于 5h 榜单的每条信息 $(s_1, p_1)$,我们需要将它与 2h 的榜单中的信息 $(s_2,p_2)$ 配对 —— 要求 $s_2\le s_1$。
若配对的 $p_1\neq p_2$,则会产生 $1$ 的修改代价。所以我们应该尽量让省份相同的信息配对。
于是转化成两张榜单信息(称之为「点」)的匹配问题。可以看成是二分图,2h 榜单和 5h 榜单分别是二分图的两个部。
一种贪心想法是按成绩从小到大依次处理 5h 榜单的信息 $(s_1,p_1)$,只考虑与相同省份的信息配对:若存在 2h 榜单的信息 $(s_2,p_2)$($s_2\le s_1,p_1=p_2$)则取 $\mathbf{s_2}$ 最大的一条信息与 $(s_1,p_1)$ 配对;否则搁置信息 $(s_1,p_1)$,当所有的信息处理完后,再进行完美匹配(无论如何匹配,这些搁置的信息都会产生 $1$ 的修改代价)。
但是这样贪心可能导致最后搁置的信息没有完美匹配。虽然题目保证最初一定有完美匹配,但是在上述贪心过程中,我们贪心地匹配了若干对点,可能导致剩下的点无法匹配。
于是我们简单修补一下这个贪心过程:若存在满足条件的 $(s_2,p_2)$,先尝试与 $(s_1,p_1)$ 配对,检验剩下的点(之前搁置的和尚未处理的)是否有完美匹配,如果有,就匹配。
检验二分图是否有完美匹配,容易想到 Hull 定理。
再加上这张二分图的连边方式非常特殊 —— 5h 榜单的信息 $(s_1,p_1)$ 与所有 2h 榜单中成绩不超过 $s_1$ 的信息(一个前缀)都有连边。
Hull 定理要求「对于“ 5h 部”的每个点集 $S$,其相邻的“ 2h 部”的点集 $T$,必须满足 $|S|\le|T|$」。
根据连边方式,若点集 $S,S’$ 的最大成绩一样,则其相邻的点集 $T$ 就一样 —— 于是我们可以等价地简化条件,对于每个 5h 榜单的前缀点集 $S$,其相邻的点集 $T$ 必须满足 $|S|\le|T|$。这样我们只需检验 $\mathcal{O}(n)$ 个前缀是否满足条件。
再对这个检验过程进行优化 —— 我们把 5h 和 2h 榜单的所有信息放在同一个序列中,按成绩从小到大排序,成绩相同则 2h 榜单的信息靠前。
将序列中 5h 榜单的信息赋值为 $-1$,2h 榜单的信息赋值为 $1$。检验等价于序列的最小前缀和大于等于 $0$。
可以用线段树维护。若检验成功,则匹配 $(s_1,p_1)$ 和 $(s_2,p_2)$,将这两个信息从线段树中删去,也就是将这两个信息的权值覆盖为 $0$。
这样检验后,能在保证合法性(存在完美匹配)的前提下保持最优性。
最后复杂度为 $\mathcal{O}(n\log n)$。
# 源代码
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
暖风捎来馥郁的飘香 栀子花海歆然盛放
我不拒绝对往事回想 也不在乎曾遍体鳞伤
只因为 岁月荏苒 你温柔的目光一如既往
看吧 我将沐火而唱
「一路有你 一路悠扬」
——《我将沐火而唱》By 豆腐P / 东方栀子 / 顾令
> Link 我将沐火而唱 - 网易云