一维阵列中匹配另一阵列位置的最小运动算法

Question

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

给定两个长度相同的位置数组(Int)，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

它的作用是: 1->2，55->99,100->3 (=142)，比1->2，55->3,100->99 (=54)更远。

有没有人可以给我指出正确的解决方案，而不是检查每一个组合？

Answer 1

我脑海中浮现的算法是

1. 排序两个数组
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;
}