Максимальная попарная разница

Если раскрыть все модули в $$$\lvert a_1 - b_{p_1} \rvert + \lvert a_2 - b_{p_2} \rvert + \ldots + \lvert a_n - b_{p_n} \rvert$$$, то $$$n$$$ чисел из $$$a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$$$ войдут в сумму со знаком плюс, а оставшиеся $$$n$$$ чисел со знаком минус.

Поэтому, максимальный счёт точно не может быть больше чем «сумма $$$n$$$ максимальных чисел среди $$$a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$$$ минус сумма $$$n$$$ минимальных чисел среди $$$a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$$$». И оказывается, что такого счёта всегда можно достичь.

Давайте отсортируем все числа $$$a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$$$ и посмотрим: сколько чисел из массива $$$a$$$ окажется в первой половине отсортированного массива, пусть $$$x$$$. Тогда чисел из массива $$$b$$$ в первой половине всего $$$n-x$$$ штук. А во второй половине: $$$n-x$$$ чисел из массива $$$a$$$, и $$$x$$$ чисел из массива $$$b$$$. Поэтому мы можем образовать $$$n$$$ пар: «число из массива $$$a$$$, число из массива $$$b$$$» так, что в каждой паре по одному числу из каждой половины отсортированного массива. И счёт в таком случае, будет в точности равен «сумма $$$n$$$ максимальных чисел среди $$$a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$$$ минус сумма $$$n$$$ минимальных чисел среди $$$a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$$$».

А число способов это сделать будет $$$x! \cdot (n-x)!$$$, где $$$k! = 1 \cdot 2 \cdot \ldots \cdot k$$$. Так как нужно независимо сопоставить $$$x$$$ наименьшим числам из $$$a$$$ — $$$x$$$ наибольших чисел из $$$b$$$, и независимо $$$n-x$$$ наибольшим числам из $$$a$$$ — $$$n-x$$$ наименьших чисел из $$$b$$$.

При этом при любом другом способе, хотя бы одна из пар $$$(a_i, b_{p_i})$$$ будет содержать пару чисел из одной и той же половины отсортированного массива, и, так как все числа различны, в таком случае счёт будет не максимален.

Асимптотика решения: $$$O(n \log n)$$$, из-за сортировки массива.