如何从k个交换中的2个数组中获得最小加法结果？

Question

我运行遇到了一个有趣的算法（也许 :/）问题，由于我刚刚开始学习算法和数据结构，所以我有点难以解决。能不能请你看看，也许能给我一些建议:)

问题如下：有两个长度相同的整数数组-n，一个开关数k，允许至多k次在2个数组之间交换，如何找到k交换后的最小加法结果？

重要的是：

Between 2 swaps, the elements should come form same array!

It may be a little confusing........ here is the example:

ex:           
     {1, 5, 3, 2, 4}  Array A          
     {3, 4, 1, 6, 2}  Array B       
     k - 2            Max swap chance 
     the minimum result should be 1-A[0] + 4-B[1] + 1-B[2] + 2-A[3] + 4-A[4] = 12
                                      first swap         second swap
                                       A -> B               B -> A
There is path like :
                      1        2   4
                         4  1

请注意：

If we choose A[0] (because A[0] < B[0] ), then Array A have to be the base array.

And the swap here:  1 A[1] ->  4 B[1]  is the first swap 
                    after above swap, the next number have to be 1 (B[2]) if we do not do another swap from B to A
                    1 A[3] ->  2 B[3] is the second swap

在我的例子中：

我们在数组A中选择1，那么第一次swap(replace)发生在A[1]和B[1]之间，在 A[3] 处发生第二次交换后，我们现在无法进行更多交换，因为 k 已达到 2（k 应该 <= 2）

在以下情况下：

          {1 5 3 7 1 1 3}
          {3 1 4 1 3 9 2}
             ^       ^
 if we only have at most 2 chance to swap, they should happen at '^' because 
           1         1 3
             1 4 1 3       
 could result in minimum addition result

让它更通用：

     {1, 5, ... , 3, ... , 2, 4}  Array A          
     {3, 4, ... , 1, ... , 6, 2}  Array B       
     k - n            Max swap chance 
     The key point here is: how could I decide whether the first swap should still
happen between A[1] and B[1] or there may be another better chance to do a swap
between A[i-th] and B[i-th] .
     And we only have at most k times swap chance, so when and where should the
k swaps happen need to be considered carefully..

我尽量把问题说清楚，如果还有什么不明白的，请告诉我。关于如何决定交换位置和交换次数并最终获得最小计算结果的任何想法？非常感谢！

Answer 1

好吧，如果我没听错，你有 2 种可能性：

交换每对第 i 个项目的项目，使 A 数组包含最少的项目
交换每对第 i 个项目的项目，使 B 数组包含最少的项目

你的情况：

让 A 有最少的物品：

 {1, 5, 3, 2, 2}  Array A          
 {3, 4, 1, 6, 4}  Array B     
 ---------------
 {1  4  1  2  2}  Min (based on A, 2 swaps)
     ^  ^
     swap (we take items from B)

让 B 有最少的项目：

 {1, 5, 3, 2, 2}  Array A          
 {3, 4, 1, 6, 4}  Array B     
 ---------------
 {1  4  1  2  2}  Min (based on B, 3 swaps)
  ^        ^  ^
     swap (we take items from A)

这里 2 < 3 所以我们应该让 A 包含最少的项目，我们可以在 2 交换中做到这一点

到目前为止，一般情况下你可以

使 A 包含每对的最少项所需的交换次数（假设为 swapsA）。
使 B 包含每对的最少项所需的交换次数（假设为 swapsB）。
ReturnMin(swapsA, swapsB)

可能C#代码

int[] A = ...
int[] B = ...

int swapsA = 0;
int swapsB = 0;

int sum = 0;

for (int i = 0; i < A.Length; ++i) {  
  sum += Math.Min(A[i], B[i]); 

  if (A[i] > B[i]) 
    swapsA += 1; 
  else if (A[i] < B[i]) 
    swapsB += 1;
}

int swaps = Math.Min(swapsA, swapsB);

Console.Write($"We have to make at least {swaps} swaps; the min sum is {sum}");

编辑： 唯一的困难是项目相等，例如

 {1, 5, 1, 2, 4}  Array A  # note that 3d and 4th pairs have equal items        
 {3, 4, 1, 2, 2}  Array B     
 ---------------
 {1  4  1  2  2}  Min (based on A, 1 swap)
     ^        ^
     swap (we take items from B)

让 B 有最少的项目：

 {1, 5, 1, 2, 4}  Array A          
 {3, 4, 1, 2, 2}  Array B     
 ---------------
 {1  4  1  2  4}  Min (based on B, 2 swaps)
  ^           
     swap (we take items from A)

请注意，一般情况下 swapsA + swapsB <= A.Length

编辑 2： 如果您有多达 K 个交换要执行，您可以订购它们并获得 K 最有希望的（最大 A[i] - B[i] 差异）：

让我们交换并求和A

      {1 5 3 7 1 1 3} A 
      {3 1 4 1 3 9 2} B
         ^   ^     ^
         reasonable swaps - 3 - more than allowed 2

      {5, 1} drops sum by 5 - 1 == 4 # most promising (a best sum drop)
      {7, 1} drops sum by 7 - 1 == 6 # most promising (a best sum drop)
      {3, 2} drops sum by 3 - 2 == 1

最有希望的交换是 {7, 1} 和 {5, 1}。所以我们有 1 + 1 + 3 + 1 + 1 + 1 + 3。

让我们交换并求和A

      {1 5 3 7 1 1 3} A 
      {3 1 4 1 3 9 2} B
       ^   ^   ^ ^ 
       reasonable swaps - 4 - more than allowed 2

      {1, 3} drops sum by 3 - 1 == 2 # most promising (a best sum drop)
      {3, 4} drops sum by 4 - 3 == 1
      {1, 3} drops sum by 3 - 1 == 2  
      {1, 9} drops sum by 9 - 1 == 8 # most promising (a best sum drop)

所以我们有 {1, 3} 和 {1, 9} 交换更有希望，总和是 1 + 1 + 4 + 1 + 3 + 1 + 2。

最后你应该比较两种可能性（如果你从 A 或 B 得到最小总和）

如何从k个交换中的2个数组中获得最小加法结果？

How to get the minimum addition result from 2 arrays within k swaps?

language-agnostic

arrays

algorithm