Editorial for Perfect Pairing

Approach

Let the sorted versions of the arrays be $a_1 \le a_2 \le \dots \le a_n$ and $b_1 \le b_2 \le \dots \le b_n$.

Consider any matching after both arrays are sorted. If there are two pairs that cross, say $a_i$ is matched with $b_q$ and $a_j$ is matched with $b_p$, where $i < j$ but $p < q$, then swapping those two pairs cannot increase the total cost.

Intuitively, crossing lines are wasteful: the smaller value from $a$ should not skip past the smaller value from $b$ while the larger value from $a$ goes backward. Repeatedly uncrossing pairs produces an optimal matching with no crossings, and the only non-crossing perfect matching is $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$.

So the algorithm is:

1. Sort both arrays.
2. Pair them in order.
3. Sum $|a_i - b_i|$.

This runs in $O(n \log n)$ because of sorting.

Solution (Python)

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

a.sort()
b.sort()

answer = 0
for x, y in zip(a, b):
    answer += abs(x - y)

print(answer)