arrays - 一维阵列中的最小移动算法以匹配另一个阵列的位置

Question

我正在尝试解决这个算法练习：

给定两个长度相同的位置（整数）数组，A 和 B，主题是找到元素在 A 处的最小移动以覆盖 B 的所有位置。

示例：A：[1, 3] B：[2, 4]。

答案：2 (1->2, 3->4, (2-1)+(4-3)=2)

我试图检查所有可能的组合，但它太慢了。

我还尝试从 B 处元素的最近位置 A 中查找每个元素，但在某些特定情况下会失败：

[1, 55, 100] [2, 3, 99]

它会做：1->2、55->99、100->3 (=142)，这比 1->2、55->3、100->99 (=54) 更远。

有人可以在不检查每个组合的情况下为我指出正确的解决方案吗？

标签： arraysalgorithm

Answer 1

我想到的算法是

1. 对 2 个数组进行排序
2. 检查在特定索引处哪个更大
3. 将它们的减法添加到变量中

这是我用 C++ 生成的代码

#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
    int n;
    cin>>n; int a[n],b[n]; int ans=0; //Assuming you are given array size 
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];    
        
    sort(a,a+n); sort(b,b+n);
    for(int i=0;i<n;i++){
        if(a[i]>b[i])
            ans+=(a[i]-b[i]);
        else
            ans +=(b[i]-a[i]);
    }
    cout<<ans;
}