数学、贪心、排序、邻项交换法

下文中使用 $ans$ 表示 $\sum\limits_{i=1}^{n} a_i \times b_i$ 以简化公式。

将序列 $a$ 和序列 $b$ 分别从小到大排序后 $ans$ 的值最大，证明：

首先将序列 $a$ 排序，考虑使用序列 $b$ 匹配序列 $a$。

对于序列 $b$ 的两种排列方式，如果它们对应的 $ans$ 相同，就认为逆序对数更小的排列方式更优，否则认为对应 $ans$ 更大的排列方式更优。

现在证明交换 $b$ 中一个相邻逆序对的元素能够使 $b$ 变优。这里使用 $b_i,b_j(i<j)$ 表示这个逆序对。

Part 1：$a_i = a_j$

交换后 $ans$ 不变，逆序对数减少，所以交换后的 $b$ 更优。

Part 2：$a_i < a_j$

$$\because a_i<a_j,b_i>b_j$$

$$\therefore (a_i \times b_j + a_j \times b_i) - (a_i \times b_i + a_j \times b_j) = a_i \times (b_j - b_i) + a_j \times (b_i - b_j)$$

$$=(b_i - b_j) \times (a_j - a_i) > 0$$

因为交换后 $ans$ 增加，交换后的 $b$ 更优。

现在已经证明了交换 $b$ 中一个相邻逆序对的元素能够使 $b$ 变优。

假设非有序的 $b$ 最优，那么交换 $b$ 中一个相邻逆序对能够得到一个优于最优解的解，因此非有序的 $b$ 必定不是最优的。

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