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

Question

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

示例:

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

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

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