给定2个数组，找到索引乘法的最小和 [英] Given 2 arrays, find the minimal sum of multiplication of indexes

问题描述

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

Suppose I have 2 unsorted arrays of the same size, for example:

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

我想求出每2个像元的最小乘法总和-每个数组一个，表示- A [i] * B [j] （ i 是 A 的索引， j 是 B ）。为了获得最小的乘积，我应该将哪个值与另一个数组中的值相乘？

I would like to find the minimal sum of multiplying of every 2 cells - one from each array, meaning - the sum of A[i] * B[j] (i is an index in A, j is an index in B). which values should I multiply with which values from the other array in order to get that minimal sum of products?

（我希望很明显，一旦执行了 A [i] * A [j] 您不能再触摸这些单元格...）

(I hope it's clear that once you performed A[i]*A[j] you can't touch those cells again...)

编辑：例如上面的最小和为：
1 * 4 + 3 * 5 + 5 * 2 + 1 * 12 = 31

edit: for the example above, the minimal sum is: 1*4 + 3*5 + 5*2 + 1*12 = 31

推荐答案

为了找到最小的总和，请先将一组升序，另一组降序，然后再按类似的指数相乘。

In order to find the smallest summation, order one set ascending, the other descending, and then multiply along the like indecies.

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

This is because the smallest possible product for each pairing a[i] * b[j] (for a fixed a[i] due to the need to have a result for each element) is the smallest possible value of b[j], and vice-versa.

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

This will also work with negatives because the greatest negative is the smallest number, and thus pairs with the most positive number from the corollary array. This further continues even when both sets are completely negative, because the result of each multiplication become equivalent to when both sets have the negatives of their values.

这篇关于给定2个数组，找到索引乘法的最小和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！