Make k Equal
Contest: Codeforces Round 629 (Div. 3)
Difficulty rating: 2200
Tags: greedy

You are given the array $$$a$$$ consisting of $$$n$$$ elements and the integer $$$k \le n$$$.

You want to obtain at least $$$k$$$ equal elements in the array $$$a$$$. In one move, you can make one of the following two operations:

- Take one of the minimum elements of the array and increase its value by one (more formally, if the minimum value of $$$a$$$ is $$$mn$$$ then you choose such index $$$i$$$ that $$$a_i = mn$$$ and set $$$a_i := a_i + 1$$$);
- take one of the maximum elements of the array and decrease its value by one (more formally, if the maximum value of $$$a$$$ is $$$mx$$$ then you choose such index $$$i$$$ that $$$a_i = mx$$$ and set $$$a_i := a_i - 1$$$).

Your task is to calculate the minimum number of moves required to obtain at least $$$k$$$ equal elements in the array.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$ and the required number of equal elements.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

Output format:
Print one integer — the minimum number of moves required to obtain at least $$$k$$$ equal elements in the array.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6 5
1 2 2 4 2 3

Example output:
3

Example input:
7 5
3 3 2 1 1 1 3

Example output:
4

Editorial:
This problem is just all about the implementation. Firstly, let's sort the initial values and compress them to pairs $$$(i, cnt[val])$$$, where $$$cnt[val]$$$ is the number of elements $$$val$$$. The first observation is pretty standard and easy: some equal elements will remain unchanged. So let's iterate over all elements $$$val$$$ in some order and suppose that all elements $$$val$$$ will remain unchanged. Firstly, we need $$$need = max(0, k - cnt[val])$$$ elements which we should obtain by some moves. The second observation is that we first need to take elements from one end (only less or only greater) and only then from the other (if needed).
Consider the case when we first take less elements. The other case is almost symmetric.
Let $$$needl = min(need, prefcnt_{prv})$$$ be the number of less than $$$val$$$ which we need to increase to $$$val$$$. If $$$needl = 0$$$ then skip the following step. Otherwise, let $$$prefcnt_i$$$ be the number of elements less than or equal to $$$i$$$, $$$prefsum_i$$$ be the sum of all elements less than or equal to $$$i$$$ and $$$prv$$$ be the previous value (the maximum value less than $$$val$$$). Then we need to increase all elements less than or equal to $$$prv$$$ at least to the value $$$val-1$$$. It costs $$$(val - 1) \cdot prefcnt_{prv} - prefsum_{prv}$$$ moves. And then we need $$$needl$$$ moves to increase $$$needl$$$ elements to $$$val$$$.
And let $$$needr = max(0, need - needl)$$$ be the number of elements greater than $$$val$$$ which we need to decrease to $$$val$$$ if we increased $$$needl$$$ elements already. If $$$needr = 0$$$ then skip the following step. Otherwise, let $$$sufcnt_i$$$ be the number of elements greater than or equal to $$$i$$$, $$$prefsum_i$$$ be the sum of all elements greater than or equal to $$$i$$$ and $$$nxt$$$ be the next value (the minimum value greater than $$$val$$$). Then we need to decrease all elements greater than or equal to $$$prv$$$ at least to the value $$$val+1$$$. It costs $$$sufsum_{nxt} - (val + 1) \cdot sufcnt_{nxt}$$$ moves. And then we need $$$needr$$$ moves to decrease $$$needr$$$ elements to $$$val$$$.
So we can update the answer with the sum of values described above and proceed to the next value. Arrays $$$prefcnt, sufcnt, prefsum, sufsum$$$ are just simple prefix and suffix sums which can be calculated in $$$O(n)$$$ using very standard and easy dynamic programming. Don't forget about the overflow.
Total time complexity: $$$O(n \log n)$$$ because of sorting.