No.615 集合に分けよう
ミドリムシ
はむこThis statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Problem Statement
There are $N$ integers, $a_1, a_2, ... a_n$.
We want to divide these $N$ integers into $K$ sets.
Here, the size of a set is defined as the difference between the maximum and minimum values of the elements contained in that set.
For example, the set {$1, 7, 4$} has maximum value $7$ and minimum value $1$, so the size of this set is $7-1=6$.
We want to divide them skillfully so as to minimize the sum of the sizes of the sets after division.
Find the minimum possible sum of the sizes of the sets after division.
Here, dividing $p$ integers into $q$ sets $x_1, x_2 ... x_q$ means that the following condition is satisfied.
・Let set $X$ denote the set with $p$ elements obtained by combining all the elements of sets $x_1, x_2, ... x_q$. Then, the elements of set $X$ and the $p$ integers are in one-to-one correspondence when equal numbers are matched with each other.
Input
$N$ $K$ $a_1$ $a_2$ ... $a_n$
$1 \leq K \leq N \leq 5 \times 10^4$
$0 \leq a_i \leq 10^{12}$
Output
Output the answer. Include a newline at the end.
Note
The numbers handled in this problem may be $2^{31}$ or greater.
Sample
Sample 1
Input
5 2 1 10 11 2 9
Output
3
If we divide them into the set {$11, 9, 10$} and the set {$2, 1$},
the size of {$2, 1$} is $2 - 1 = 1$ and
the size of {$11, 9, 10$} is $11 - 9 = 2$,
so the sum of the sizes of the sets after division is $3$, and this is the minimum.
Sample 2
Input
4 2 0 7 3 13
Output
7
The minimum can be achieved by dividing them into the set {$0, 7, 3$} and the set {$13$}.
Sample 3
Input
3 3 1 10 100
Output
0
The minimum can be achieved by dividing them into the set {$1$}, the set {$10$}, and the set {$100$}.
Sample 4
Input
3 1 0 0 1000000000000
Output
1000000000000
The only possible division is into the set {$0, 0, 1000000000000$}, and this gives the minimum.
Beware of overflow.
Sample 5
Input
10 3 1 12 19 23 28 3 32 36 41 7
Output
28
The minimum can be achieved by dividing them into the set {$12$}, the set {$28, 23, 41, 19, 32, 36$}, and the set {$3, 1, 7$}.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。