1. Идея

Нужно разбить игроков двух клубов на пары так, чтобы сумма |a_i - b_j| была минимальной.

Главная идея очень простая:
если отсортировать рейтинги обоих клубов, то оптимально соединять игроков с одинаковыми позициями в этих отсортированных списках:

• самого слабого с самым слабым,
• второго по силе со вторым,
• ...
• самого сильного с самым сильным.

После этого ответ равен сумме |a[i] - b[i]| по всем индексам.

2. Наблюдения

Пусть есть два отсортированных массива:

• a[0] <= a[1] <= ... <= a[n-1]
• b[0] <= b[1] <= ... <= b[n-1]

Почему нельзя получить лучший ответ, если "перекрещивать" пары?

Рассмотрим два игрока из первого клуба: a[i] и a[j], где i < j, значит a[i] <= a[j].

И двух игроков из второго клуба: b[k] и b[l], где k < l, значит b[k] <= b[l].

Сравним два способа составить пары:

1. без пересечения:

   • a[i] с b[k]
   • a[j] с b[l]

2. с пересечением:

   • a[i] с b[l]
   • a[j] с b[k]

Оказывается, второй вариант никогда не лучше первого.
Интуитивно это понятно: если маленький элемент соединять с большим, а большой — с маленьким, разницы становятся только хуже.

Значит, в оптимальном ответе пары можно упорядочить без пересечений, а это как раз и приводит к попарному сопоставлению после сортировки.

3. Алгоритм

1. Считать n.
2. Считать массив рейтингов первого клуба a.
3. Считать массив рейтингов второго клуба b.
4. Отсортировать a.
5. Отсортировать b.
6. Пройти по всем индексам от 0 до n - 1 и прибавить к ответу abs(a[i] - b[i]).
7. Вывести ответ.

4. Почему это работает

Докажем, что описанный алгоритм действительно даёт минимальную сумму.

Рассмотрим любое паросочетание между игроками двух клубов. После сортировки элементов можно представить пары как соединения между позициями в массивах a и b.

Ключевой шаг

Покажем, что если в паросочетании есть "перекрёстные" пары, то их можно заменить на неперекрёстные, не увеличив ответ.

Пусть есть:

• a[i] <= a[j]
• b[k] <= b[l]

и пары:

• a[i] с b[l]
• a[j] с b[k]

Их вклад в сумму равен:

|a[i] - b[l]| + |a[j] - b[k]|

Если заменить их на:

• a[i] с b[k]
• a[j] с b[l]

то вклад станет:

|a[i] - b[k]| + |a[j] - b[l]|

Для упорядоченных чисел второй вариант не больше первого.
Значит, любое пересечение можно убрать без ухудшения ответа.

Что из этого следует

Если последовательно убирать все пересечения, мы придём к паросочетанию без пересечений.

Но единственное полное непересекающееся сопоставление двух отсортированных массивов — это pairing по индексам:

• a[0] с b[0]
• a[1] с b[1]
• ...
• a[n-1] с b[n-1]

Следовательно, именно такая схема даёт минимальную возможную сумму.

5. Сложность

Сортировка двух массивов длины n занимает O(n log n).

После этого один проход для подсчёта суммы работает за O(n).

Итоговая сложность: O(n log n).

Дополнительная память: O(1), если не считать хранение входных массивов.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += llabs(a[i] - b[i]);
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort()

ans = 0
for i in range(n):
    ans += abs(a[i] - b[i])

print(ans)