Перестановка двох масивів#12967

Перестановка двох масивів (Editorial)

Без обмеження загальності вважатимемо, що . Впорядкуємо масив у порядку зростання, а масив у порядку спадання. Оскільки ми хочемо максимізувати відстань, то з масиву вигідно брати лише елементи на префіксі та суфіксі. Переберемо —кількість елементів з префіксу ми беремо, та паруємо їх з суфіксом масиву . Відповідно префікс масиву довжини n - len паруємо з суфіксом масиву . Тоді відповідь буде рівною

\max_{len \in [0, n]} (\sum_{i=n-len}^{n - 1} a_i - \sum_{i=0}^{len} b_i) + (\sum_{i=m-len}^{n - 1} b_i - \sum_{i=0}^{len} a_i)

.

Таку формулу можна рахувати за допомогою часткових сум, або перераховувати доданки в процесі зміни .

Складність .