Блог

Я пытаюсь решить это упражнение по алгоритму:

Учитывая два массива позиций (целых чисел) одинаковой длины, A и B, задача состоит в том, чтобы найти минимальное перемещение элементов в A, чтобы покрыть все позиции B.

Пример: A: [1, 3] B: [2, 4].

Ответ: 2 (1->2, 3->4, (2-1) (4-3)=2)

Я пытался проверить все возможные комбинации, но это слишком медленно.

Я также пытался найти для каждого элемента ближайшую позицию элемента в B, но в некоторых конкретных случаях это не удается:

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

Это сделало бы: 1->2, 55->99, 100->3 (=142), что находится дальше, чем 1->2, 55->3, 100->99 (=54).

Может ли кто-нибудь указать мне правильное решение, не проверяя каждую комбинацию?

Алгоритм, который приходит мне на ум, таков

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;
}