两个数组的最小总和，选择每个数组中的一半元素

Question

你好，我不是一个所谓的专业程序员。我有两个阵列a1和a2的integers具有相同的均匀长度n。我需要通过为每个索引选择一个元素来找到a1和a2中元素的最小总和，并且所选元素的一半应该位于a1中，其余元素位于a2中。

例：

 a1 = [36, 72];  
 a2 = [35, 61];

结果应该是97，因为我们应该选择来自36的a1和来自61的a2。我认为一种解决方案是在n/2和a1中选择所有可能的a2元素并计算它们的结果。可以找到更有效的解决方案吗？

Answer 1

让我们重新编写阵列a1和a2

    a1 = [36, 72];  
    a2 = [35, 61];

以不同的方式：我们组合第i个索引并计算penalty = a2[i] - a1[i]：

    a = [(36, 35; penalty = -1), (72, 61; penalty = -11)]

这里penalty是我们选择a2值而不是a1时必须支付的价格。让我们按罚分类

    a = [(72, 61; penalty = -11), (36, 35; penalty = -1)]

现在让我们选择惩罚最低的n/2项目，并采取a2项目;选择惩罚最高的n/2项目并采取a1项目：

    a = [(72, 61; penalty = -11), (36, 35; penalty = -1)]
         (72, 61; penalty = -11) - lowest,  take a2 item - 61
         (36, 35; penalty = -1)  - highest, take a1 item - 36

时间复杂性是O(n * log(n)) - 排序。

C＃实现：

  using System.Linq;

  ...

  int[] a1 = new int[] { 36, 72 };
  int[] a2 = new int[] { 35, 61 };

  var result = Enumerable
    .Range(0, a1.Length)
    .Select(i => new {
      v1 = a1[i],
      v2 = a2[i],
    })
    .OrderByDescending(item => item.v1 - item.v2)
    .Select((item, index) => index >= a1.Length / 2 
       ? item.v1 
       : item.v2)
    .Sum();

  Console.WriteLine(result);

结果：

  97

Answer 2

选择所有可能的n / 2元素并寻找最小元素将起作用，但成本非常高。特别地，运行时复杂度将是O（n ^ n）。

基本的想法是你想要在索引i选择具有高差异|a1[i] - a2[i]|的元素。这是一个算法草图：

1. 在d[i] = |a1[i] - a2[i]|中构建一个新的数组d
2. 现在按照i的降序索引d。所以d中最大元素的指数首先是d中第二大元素的指数，依此类推。
3. 对于你从第2步得到的每个指数i。取a1[i]和a2[i]的较小元素并将其加到你的总和中。您还将跟踪从a1中获取的元素数量以及a2中的元素数量。如果在某一点上你使用了n/2，你可以用其他数组中的剩余条目填充总和。

例：

a1 = [11, 12, 13, 12]

a2 = [15, 2,  30, 14]

d  = [4 , 10, 17, 2]

所以这里首先选择a1 [2]（13），因为d [2]是d中最大的元素，a1 [2] <a2 [2]。接下来你选择a2 [1]（2），因为d [1]是d中的第二大元素。接下来你选择a1 [0]（11）因为和以前一样的推理。最后，你意识到你已经从a1中选择了两个元素，这就是为什么你将所有剩余的元素从a2添加到你的总和（14）。结果是13 + 2 + 11 + 14 = 40

当有效实现时，这可以在O（n log n）中运行