問題一覧 > 通常問題

No.615 集合に分けよう

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 245
作問者 : ミドリムシミドリムシ / テスター : はむこはむこ
31 ProblemId : 2022 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-09 11:00:10
 この問題は、Advent Calendar Contest 2017の15日目の問題です。

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。