给定2个数组,找到索引乘法的最小和

Question

假设我有2个相同大小的未排序数组,例如:

A = {1, 4, 3, 2}
B = {5, 12, 1, 5}

我想找到每2个单元的乘法的最小和 - 每个单元一个,意思是 - A[i] * B[j](i是一个索引A,j是一个索引B).我应该将哪些值与其他数组中的哪些值相乘以获得最小的产品总和？

(我希望很明显,一旦你表演了A[i]*A[j]你就不能再触摸那些细胞......)

编辑:对于上面的例子,最小和为:1*4 + 3*5 + 5*2 + 1*12 = 31

Answer 1

为了找到最小的总和，将一组升序排列，另一个降序排列，然后沿着类似的指数相乘。

这是因为每个配对的最小可能乘积a[i] * b[j]（对于一个固定的，a[i]因为需要为每个元素都有一个结果）是 的最小可能值b[j]，反之亦然。

这也适用于负数，因为最大的负数是最小的数，因此与推论数组中的最大正数配对。即使当两个集合都完全为负时，这种情况会进一步继续，因为每次乘法的结果变得等价于当两个集合的值都是负数时。