这个是原题链接

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

\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} ,使答案增大。

证明完毕!