Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

NVGU's blog

Prove answer of a problem
By NVGU, history, 11 months ago, In English

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,

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
11 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply