And*_*jia 6 sorting algorithm proof time-complexity data-structures
我有两个整数数组A，B大小均为n。一对的成本是|A(i) - B(i)|。我想将 A 和 B 的 n 个元素配对，以使所有s 和s
的所有成本之和最小化。A(i)B(i)
我知道我可以O(n log n)通过排序A，然后排序B，然后将它们1...n分别配对在一起，但是在尝试了几个小时之后，我不知道如何证明这一点。有人可以帮我吗？
我已经看到了如何实现它，但我只是不知道如何证明它
我在这里采用稍微不同的方法，通过使用平方而不是绝对值来证明这一事实。
考虑 2 个数组，A = [a1, a2, ..., an]和B = [b1, b2, ..., bn]。
现在，即使我使用随机配对（使用A和B中的任何索引形成一对），
比方说，差平方和 ( S ) = a1^2 + b1^2 + a2^2 + b2^2 + ... + an^2 + bn^2 - 2 * (a1 * b3 + a2 * b4 + .... + an * b56 + bn * a34)。
上述总和可以表示为S = sum(ai^2) + sum(bi^2) - 2 * sum(ai*bi)，其中i从 1 到 n。
为了最小化这个总和，我们需要最大化 部分sum(ai*bi)，因为i从 1 到 n。
sum(ai*bi)当 2 个数组排序时，该项将达到最大值。
感谢您指出@Abhinav Mathur：该陈述The term sum(ai*bi) will be maximum when the 2 arrays will be sorted可以使用重排不等式来证明。