Автор задачі: | Павло Ціцей |
Задачу підготували: | Павло ціцей, Олександр Тимкович |
Розбір написав: | Павло Ціцей |
Рішення — потрібно зводити кожен елемент до медіани масиву. Тобто якщо медіана це , то відповідь це \sum_{i=1}^n |a_i-x|.
Доказ:
Будемо вважати що масив відсортований. Зафіксуємо якесь і доведемо що якщо зводити елементи масиву до x+k, то відповідь буде більша або рівна за правильну. За припущенням, правильна відповідь \sum_{i=1}^n |a_i-x|.
Через те, що — це медіана, ми можемо це переписати як
Тепер запишемо відповідь для x+k.
де — це індекс останнього елементу, що менше або рівне за x+k. Якщо k>0, то y\ge\frac{n}{2} та віднявши 2 відповіді, ми отримаємо
Ми знаємо що y\ge \frac{n}{2}, тому -2\cdot x\cdot y+2\cdot x\cdot \lfloor\frac{n}{2}\rfloor\le0 and -2\cdot k\cdot y+k\cdot n\le 0, тому відповідь в цьому випадку більша або рівна. Для випадку коли k<0 рішення симетричне.