algorithm - 最小化两个数组的绝对差之和

Question

我有两个整数数组 A和 B两个尺寸n .一对的成本是|A(i) - B(i)| .
我想配对 A 和 B 的 n 个元素，使得所有成本的总和 A(i) s 和 B(i) s 被最小化。
我知道我可以得到O(n log n)按排序 A ，然后排序 B ，然后从 1...n 将它们配对在一起分别，但是在尝试了几个小时之后，我不知道如何证明这一点。有人可以帮我吗？
我已经看到如何实现它，我只是不知道如何证明它

Answer 1

假设根据当前排序的数组，有一对|x-a| , 和另一对 |y-b| .假设切换元素会得到较小的总和，即更优化的解决方案。
(注意:在切换两对时，阵列的其余部分不受影响)。

Current total sum of pairs = |x-a| + |y-b|  
Modified sum after switching pairs = |x-b| + |y-a|
Difference in sums = diff = |x-b| - |x-a| + |y-a| + |y-b|

如 diff是负数，这意味着我们找到了更好的排序。如果不是，这意味着我们原来的解决方案更好。
现在，您可以处理案例并对其进行分析。 (由于数组已排序，让 x<y(它们来自第一个数组)和 a<b(它们来自第二个数组)。

案例一:x>b或 y<a :
在这种情况下，两个和将相等，这可以通过扩展模数

很容易看出。

案例2:a<x<b :
如 y>b , diff = 2*(b-x) .由于我们假设 b>x , diff是积极的。
如 y<b , diff = 2*(y-x) .自 y>x如前所述， diff 再次为正。

你可以继续拿类似的案例来证明diff将始终为正，这意味着我们的原始排序将是最有效的排序。