CJTX03｜双队配对 题解

核心算法

两列分别排序后按相同下标配对。

思路推导

将甲队能力值和乙队能力值分别从小到大排序。第 $i$ 小的甲队同学与第 $i$ 小的乙队同学配对，累加绝对差。

正确性说明

设 $a_1\le a_2$、$b_1\le b_2$。若出现交叉配对 $(a_1,b_2)$ 与 $(a_2,b_1)$，则把它们改为顺序配对 $(a_1,b_1)$ 与 $(a_2,b_2)$，绝对差之和不会增大。不断消除所有交叉配对，最终得到两列同序配对，因此该方案最优。

复杂度

• 时间复杂度：$O(n\log n)$；
• 空间复杂度：$O(n)$。

易错点

• 两个序列都要排序；
• 不是把甲队每个人独立匹配到“当前最近”的乙队同学；
• abs 的参数与累计答案应使用 long long。