Help in a problem

Revision en1, by AliMskrc, 2018-11-16 21:58:43

We are given N numbers and in 1 move we can decrease or increase a number by 1. What is the minimal number of moves we have to do in order to have at least M same number.

In first line N and M: 1 <= M <= N <= 1e5 N numbers in second line: 1 <= numbers <= 1e9

Sample 1: 3 3 1 2 3 Output: 2 We increase 1st number by 1 and decrease last by 1. Answer is 2.

Sample 2: 3 3 1 1 1000000000 Output: 999999999 We decrease last number by 1, 999999999 times.

I sorted the array and looked in all M consecutive numbers but I don't know which number to choose when making all M numbers equal. I tried (left-most index + M/2)th number but it doesn't seem to work.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English AliMskrc 2018-11-16 21:58:43 690 Initial revision (published)