Problem Author: | Pavlo Tsitsei |
Prepared by: | Pavlo Tsitsei, Oleksandr Tymkovich |
Tutorial by: | Pavlo Tsitsei |
Solution — it is necessary to reduce each element to the median of the array. That is, if the median is , then the answer is \sum_{i=1}^n |a_i-x|.
Proof:
Let's assume that the array is sorted. Let's fix some and prove that if we reduce the elements of the array to x+k, then the answer will be greater than or equal to the correct one. By assumption, the correct answer is \sum_{i=1}^n |a_i-x|.
Since is the median, we can rewrite it as
Now let's write the answer for x+k.
where is the index of the last element that is less than or equal to x+k. If k>0, then y\ge\frac{n}{2} and subtracting 2 from the answers, we get
We know that y\ge \frac{n}{2}, so -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, so the answer in this case is greater than or equal to. For the case when k<0, the solution is symmetric.