笔记 – 关于两个序列的顺序对 的影响

这个是原题链接

关键在于发现题目是逆序对，实际上你在赛场上直接猜结论（确实需要一定的勇气，毕竟数据不够多，罚时等等）也是可以的，那么我们来推导一下这个性质。

\sum{(a_i-b_i)^2} = \sum{[a_i^2 + b_i^2 – 2a_ib_i]} = \sum{(a_i^2 + b_i^2)} – 2\sum {a_ib_i}

由于所有 a_i 与所有 b_i 相等，所以 \sum{(a_i^2 + b_i^2)} 不用考虑，考虑如何使 \sum {a_ib_i} 最大。

现在有 a_1, a_2, b_1, b_2 , a_1 \lt a_2, b_1 \lt b_2.

则有：

a_1 \times b_1 + a_2 \times b_2 – a_1 \times b_2 – a_2 \times b_1 = a_1(b_1-b_2) + a_2(b_2-b_1) = (a_1-a_2)(b_1-b_2) \gt 0

所以对于一个乱序的，即增加逆序对的个数，就会减小 \sum {a_ib_i} ，使答案增大。

证明完毕！