Блог пользователя NVGU

Автор NVGU, история, 15 месяцев назад, По-английски

Today I read the following problem that makes all elements in a sequence the same, using the minimum number of steps. Where each step increments or decrements an element by a constant integer d. And I know the minimum number of steps is the number of steps that make all elements the median of all elements. But I don't know how to prove it. please can someone help me prove it. Thanks for taking the time to read this blog,

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

If you think of it like finding a point which minimises the sum of Manhattan distance from a point x SUM( |Xi-Xm| )

https://cs.stackexchange.com/questions/61090/proof-that-median-of-an-array-is-the-number-that-minimizes-the-sum-of-manhattan