663. The Fewest Moves to Make Two Lists Match
Two lists of the same length are given. One MOVE changes any single value by 1, up or down. Make the two lists hold the SAME MULTISET of values, so order does not matter, using as few moves as possible.
Print that smallest number of moves.
1 2 and 3 4 -> 4 move 1 to 3 and 2 to 4
1 5 and 5 1 -> 0 already the same multiset
10 20 and 15 15 -> 10
## Sort both, then pair position by position
answer = sum of |sorted_a[i] - sorted_b[i]|
Two cursors walk the sorted lists together, and the moves are the gaps between what they point at.
## Why sorted pairing is optimal
The cost of a pairing is the sum of |x - y| over matched pairs. Suppose a pairing matches
x1 with y2 and x2 with y1 where x1 <= x2 and y1 <= y2, so the pairs CROSS.
Uncrossing them, to x1 with y1 and x2 with y2, never costs more. That is the
rearrangement inequality for absolute distances, and it is easy to see on a line: two crossing
segments can be replaced by two nested or disjoint ones covering no more total length.
Any pairing that is not the sorted one has a crossing somewhere, so repeatedly uncrossing reaches the sorted pairing without ever increasing the cost.
That argument is worth having, because "sort both and pair up" is a rule people apply from memory and then misapply to problems where the cost is not a distance.
## What the problem is NOT asking
It does not ask to make the lists equal POSITION BY POSITION. That version has the same answer here only because we are free to permute, and the whole point of the multiset wording is to grant that freedom.
1 5 and 5 1 answer 0 for exactly that reason, and it is the test for the misreading.
## Overflow
200000 gaps of up to 2 * 10^9 reach 4 * 10^14. Use 64 bits.
## Boundaries
Identical lists answer 0. A single value in each answers their difference.
## Cost
Time O(n log n) for the two sorts. Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers, the first list.
The third line contains n integers, the second list.
Output
Print one integer, the fewest moves needed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.