Editorial for Perfect Pairing

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Let the sorted versions of the arrays be $a_1 \le a_2 \le \dots \le a_n$ ~a_1 \le a_2 \le \dots \le a_n~ and $b_1 \le b_2 \le \dots \le b_n$ ~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$ ~a_i~ is matched with $b_q$ ~b_q~ and $a_j$ ~a_j~ is matched with $b_p$ ~b_p~, where $i < j$ ~i < j~ but $p < q$ ~p < q~, then swapping those two pairs cannot increase the total cost.

Intuitively, crossing lines are wasteful: the smaller value from $a$ ~a~ should not skip past the smaller value from $b$ ~b~ while the larger value from $a$ ~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:

Sort both arrays.
Pair them in order.
Sum $|a_i - b_i|$ ~|a_i - b_i|~.

This runs in $O(n \log n)$ ~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)

Comments

There are no comments at the moment.