No.615

$a_i$ はソートしておく.

$a_i$ を $K$ 個の集合に分けるのを考えると, ひとつの集合には連続した $a_i$ を入れるのが最適である. 連続でない $a_i$ を入れたときは, 連続になるように要素を入れ替えた方が全体の大きさが小さくなるからである.

よって, 集合のそれぞれの最初の要素を $a_{s_j}$ とすると, 集合の大きさの合計は,

$$a_N - a_i - \sum_{j=2}^{K} (a_{s_j} - a_{s_j-1})$$

となる. 右辺第二項をなるべく大きくすればいいので, $a_i$ の隣接要素の差を計算し, その中で大きい順に $K-1$ 個取ればいい.