贪心、数学、邻项交换法

题意即给定两个单调不降的序列 $a,b$，重排这两个序列使得 $\sum\limits_{i=1}^{n} \min(a_i,b_i)$ 最大。

下文中令 $ans=\sum\limits_{i=1}^{n} \min(a_i,b_i)$ 以简化公式。

Solution 1：发现 $\min( \min\limits_{i=1}^{n} (a_i), \min\limits_{i=1}^{n} (b_i))$ 一定对答案有贡献，假设 $\min\limits_{i=1}^{n} (a_i) \leq \min\limits_{i=1}^{n} (b_i)$，那么应该使用 $\min\limits_{i=1}^{n} (b_i)$ 与之配对以最小化损失，否则应当使用 $\min\limits_{i=1}^{n} (a_i)$ 配对 $\min\limits_{i=1}^{n} (b_i)$。问题规模在去掉 $\min\limits_{i=1}^{n} (a_i)$ 和 $\min\limits_{i=1}^{n} (b_i)$ 后从 $n$ 减小到 $n-1$，并且仍然可以套用上述做法。

将 $a,b$ 排序后计算答案即可最大化 $ans$，由于两个序列有序，直接计算即可。

时间复杂度 $O(n)$。

Solution 2：可以使用邻项交换法证明把有序的 $a,b$ 配对后计算得到的答案最优。

感谢 U 群群友 skip2004 老师的指导。

对序列 $a$ 排序，然后使用序列 $b$ 匹配序列 $a$，如果 $b$ 的不同重排方案得到的 $ans$ 相同则认为逆序对数少的重排方案更优，否则认为 $ans$ 更大的重排方案更优。

首先证明交换 $b$ 的相邻逆序对会使序列 $b$ 变优。假设被交换的是 $b_i,b_j(i<j)$，由于是逆序对所以有 $b_i>b_j$。

Part 1：$a_i = a_j$

交换前后 $ans$ 相同，但交换后 $b$ 的逆序对数更小所以更优。

Part 2：$a_i < a_j$

交换后的 $ans$ 减去交换前的 $ans$ 得到的值为

$$\min(a_i,b_j) + \min(a_j,b_i) - \min(a_i,b_i) - \min(a_j,b_j)$$

因为 $\min(a_i,a_j,b_i,b_j)$ 必定对答案有贡献，所以先钦定这个值。

• 若 $a_i = \min(a_i,a_j,b_i,b_j)$，则上式能够化为 $\min(a_j,b_i) - \min(a_j,b_j)$，由 $b_i>b_j$ 得到 $\min(a_j,b_i) - \min(a_j,b_j) \geq 0$。令 $N = \min(a_j,b_i) - \min(a_j,b_j)$，如果 $N=0$ 则由于逆序对数减少交换后的序列 $b$ 更优，否则由于 $ans$ 更大交换后的序列 $b$ 更优。
• 若 $b_j = \min(a_i,a_j,b_i,b_j)$，则上式能够化为 $\min(a_j,b_i) - \min(a_i,b_i)$，由 $a_i < a_j$ 得到 $\min(a_j,b_i) - \min(a_i,b_i) \geq 0$。令 $N = \min(a_j,b_i) - \min(a_i,b_i)$，同理交换后的序列 $b$ 更优。

现在已经证明了交换 $b$ 的相邻逆序对会使序列 $b$ 变优。

反证结论，如果非有序的 $b$ 最优，那么交换相邻逆序对会得到一个优于最优解的解，因此非有序的 $b$ 必定不是最优的。

于是对于有序的序列 $a$ 而言有序的序列 $b$ 最优，证毕。

时间复杂度 $O(n)$。