Beautiful Array#350

Beautiful Array (Editorial)

Автор:

Ціцей Павло

Підготували:

Ціцей Павло

Розбір:

Ціцей Павло

Нехай a_i буде відсортована послідовність. Тобто, a_i\le a_{i+1} для всіх 1\le i\le n-1. Тоді відповіддю буде послідовність a_n,\ a_{1},\ a_{n-1},\ a_{2},\ \dots.

Доведення:

Ми будемо доводити це, використовуючи математичну індукцію.

База індукції буде 2 числа. Тоді відповідь це різниця між ними.

Нехай для всіх послідовностей b_1,b_2,\dots,b_{n-1} це буде правда. Тоді доведемо для послідовності a_1,a_2,\dots,a_n. Ми знаємо, що a_{n}-a_1 буде найбільше серед всіх a_i-a_j для всіх i та j. Тоді, видалимо a_{n} з послідовності, та ми отримаємо послідовність b_1,b_2,\dots,b_{n-1}, де b_i=-a_{n-i}, і тому послідовність залишається відсортованою. Через це b_i-b_j=a_{n-j}-a_{n-i}, і тому умова про різні різниці зберігається, і там відповідь буде b_{n-1},b_1,b_{n-2},b_2,\dots, що рівно -a_1,-a_{n-1},-a_2,-a_{n-2},\dots тому також підходить послідовність a_1,a_{n-1},a_2,a_{n-2},\dots. Через те, що a_n-a_1 це найбільша можлива різниця у послідовності, ніде не зустрічається різниця, рівна цій. А тому, ми можемо додати на початок a_n, і тому рішення доведено.