Автор: | Ціцей Павло |
Підготували: | Ціцей Павло |
Розбір: | Ціцей Павло |
Нехай 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, і тому рішення доведено.