题意:
给出两个数组 a1,2,…,na_{1,2,\dots,n}a1,2,…,n 以及 b1,2,…,nb_{1,2,\dots,n}b1,2,…,n,要求每个 aaa 数组里的每个数与 bbb 数组里的每个数两两配对,使 ∑i=1n∣ai−bi∣\sum_{i=1}^n |a_i -b_i|∑i=1n∣ai−bi∣ 最小。
样例:
输入 4 1 2 3 4 5 6 7 8 输出 16
出乎我的意料,这一题正解竟然是把两个数组排序过后直接输出 ∑i=1n∣ai−bi∣\sum_{i=1}^n |a_i -b_i|∑i=1n∣ai−bi∣。
求证正确性。