Суперскеляста місцевість (Розбір)

Одним із можливих розташувань є:

Тобто потрібно у відсортованій перестановці поміняти місцями числа на позиціях $2k$ і 2k + 1 для $k$ від $1$ до \bigl\lfloor (n - 1)/2\bigr\rfloor. Часова складнiсть $O(n)$, адже нам не потрібно сортувати, бо набір елементів відомий із самого початку.

До речі, початкова версія цієї задачі була складнішою, проте було прийнято рішення замінити її на легшу. У початковій версії задачі давався масив із довільних $n$ чисел, а не перестановка. Для розв'язання складнішої версії треба було спочатку відсортувати числа і розділити їх на дві половини. Нехай b_1, b_2, \dots, b_n — відсортований масив, тоді поділимо його на дві частини: small = \{b_1, b_2, \dots, b_{\bigl\lceil n/2\bigr\rceil}\} і large = \{b_{\bigl\lceil n/2\bigr\rceil + 1}, \dots, b_{n}\}. Далі будемо по черзі діставати елементи з кінця $small$ та large і додавати їх до масиву res = \{small_{\text{last}}, large_{\text{last}}, small_{\text{last} - 1}, \dots\}. Суперскелясту місцевість вдасться сформувати тільки якщо $res$ задовольняє умову res_1 < res_2 > res_3 < res_4 \dots Загальна часова складність цього способу буде O(n\log{n}) через необхідність сортування.