When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

AliMskrc's blog

By AliMskrc, history, 5 years ago, In English

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.

  • Vote: I like it
  • -6
  • Vote: I do not like it