Minimizing Sum Problem, need help!

Правка en2, от Kaleab_Asfaw, 2020-08-01 21:08:12

Problem from "Competitive Programmer’s Handbook" by Antti Laaksonen, Page 61.

The problem is to find x to minimum the sum of the equation below:

Image

I thought the answer will be the mean on the number because if we plot the in a 1D number line, the mean will be somewhere middle of them, so the absolute difference of distance between each number and the mean can be minimized.

The book says it is the median.

Example [1, 2, 2, 6, 9]

The mean will be 19 / 5 = 3.8. The absolute difference is 13.8.

The median is 2 an the absolute difference is 12.

I know that this is the absolute sum not the just the sum. But the median is only limited to the element of the array. Why x should be the median instead of the mean? Can this be mathematically proved?

Теги help, sum, logic

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Kaleab_Asfaw 2020-08-01 21:08:12 46 Tiny change: 'oXSDt)\n\nI tho' -> 'oXSDt)\n\n[Image](https://pasteboard.co/JknMyWb.png)\n\nI tho'
en1 Английский Kaleab_Asfaw 2020-08-01 21:03:43 913 Initial revision (published)