2 个列表/数组中的一对中的最小元素

Question

我有 2 个排序整数列表或数组a和b，两者都具有相同数量的元素。我想将a中的元素与b中的元素配对，这样当我在所有对中获取较小的元素时，它们的总和是最小的。 例如

a=[1,7,14,18]
b=[8,9,10,12]

我将配对[(1,12),(7,10),(14,9),(18,8)]然后在每对中取较小的元素，即[1,7,9,8]，我将得到最小和。这只是我采取的一种可能性。我想知道这种将第一个列表的元素从第一个元素配对并从尾向后移动第二个列表的元素的方法是否会给我最小总和。

Answer 1

是的，将最大与最小配对的方法将起作用：

1. 如果第二个数组中的最大元素小于第一个数组中最小的元素，则任何配对方法都将起作用，因此使用您的方法配对其余元素。
如果没有，将第一对
2. 与您的方法配对将确保计算第一对中的最小(应计算(和第二对中的最大(不应计算(将不计算在内
3. 对两个数组中的其余元素重复步骤 1 和 2，直到元素用完

如您所见，数组中最小的剩余元素将始终在沿途的每一步进行计数，因此结果对中最小的元素的总和将根据需要最小化。