Паша також проти "хвостів"?#19

Паша також проти "хвостів"? (Розбір)

Автор задачі:

Павло Ціцей

Задачу підготували:

Павло ціцей, Олександр Тимкович

Розбір написав:

Павло Ціцей

Рішення — потрібно зводити кожен елемент до медіани масиву. Тобто якщо медіана це , то відповідь це \sum_{i=1}^n |a_i-x|.

Доказ:

Будемо вважати що масив відсортований. Зафіксуємо якесь і доведемо що якщо зводити елементи масиву до x+k, то відповідь буде більша або рівна за правильну. За припущенням, правильна відповідь \sum_{i=1}^n |a_i-x|.

Через те, що — це медіана, ми можемо це переписати як

\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x-a_i+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^{n}a_i-x

Тепер запишемо відповідь для x+k.

\sum_{i=1}^n |a_i-x-k|=\sum_{i=1}^y x+k-a_i+\sum_{i=y+1}^n a_i-x-k

де — це індекс останнього елементу, що менше або рівне за x+k. Якщо k>0, то y\ge\frac{n}{2} та віднявши 2 відповіді, ми отримаємо

\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x-a_i+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^{n}a_i-x-\sum_{i=1}^y x+k-a_i-\sum_{i=y+1}^n a_i-x-k=
\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x-a_i-x-k+a_i+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^y a_i-x-x-k-a_i+\sum_{i=y+1}^{n}a_i-x-a_i+x+k=
\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}-k+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^y -2\cdot x-k+\sum_{i=y+1}^{n}k=
-k\cdot\lfloor\frac{n}{2}\rfloor-2\cdot x\cdot (y-\lfloor\frac{n}{2}\rfloor)-k\cdot (y-\lfloor\frac{n}{2}\rfloor)+k\cdot(n-y)=-2\cdot x\cdot y+2\cdot x\cdot \lfloor\frac{n}{2}\rfloor-2\cdot k\cdot y+k\cdot n

Ми знаємо що 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 рішення симетричне.