No.615 集合に分けよう
タグ : / 解いたユーザー数 251
作問者 :
ミドリムシ
/ テスター :
はむこ
問題文
$N$個の整数があり、それぞれ$a_1, a_2, ... a_n$である。
この$N$個の整数を$K$個の集合に分けたい。
ここで、集合の大きさを その集合に含まれる要素の最大値と最小値の差 と定義する。
例えば、集合{$1, 7, 4$}は最大値が$7$で最小値が$1$なので、この集合の大きさは$7-1=6$になる。
上手く分けて、分けた後の集合の大きさの総和を最小化したい。
分けた後の集合の大きさの総和の最小値を求めなさい。
ただし、$p$個の整数を$q$個の集合$x_1, x_2 ... x_q$に分ける とは、次の条件を満たしているということである。
・集合$x_1, x_2, ... x_q$の要素を全て合わせた要素数$p$の集合を 集合$X$ と呼ぶことにすると、集合$X$の各要素と$p$個の各整数は同じ数同士を対応させると1対1対応する。
入力
$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}$
出力
答えを出力せよ。 末尾に改行を入れること。
注意
この問題で扱う数値が$2^{31}$以上になる可能性がある。
サンプル
サンプル1
入力
5 2 1 10 11 2 9
出力
3
集合{$11, 9, 10$}と集合{$2, 1$}に分けると、
{$2, 1$}の大きさは$2 - 1 = 1$
{$11, 9, 10$}の大きさは$11 - 9 = 2$
となるので、分けた後の集合の大きさの総和は$3$になり、これが最小値である。
サンプル2
入力
4 2 0 7 3 13
出力
7
集合{$0, 7, 3$}と集合{$13$}に分けることで、最小値を達成できる。
サンプル3
入力
3 3 1 10 100
出力
0
集合{$1$}と集合{$10$}と集合{$100$}に分けることで、最小値を達成できる。
サンプル4
入力
3 1 0 0 1000000000000
出力
1000000000000
集合{$0, 0, 1000000000000$}に分けることしか出来ず、この時が最小値になる。
オーバーフローに注意。
サンプル5
入力
10 3 1 12 19 23 28 3 32 36 41 7
出力
28
集合{$12$}と集合{$28, 23, 41, 19, 32, 36$}と集合{$3, 1, 7$}に分けることで、最小値を達成できる。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。