概要

\(N\) 個のりんごを \(K\) 個の箱に分けて、各箱の「重さの最大値と最小値の差」の合計を最小にする問題。

考察

この問題のポイントは、「各箱のばらつき度の合計を小さくする」には、重さが近いりんごを同じ箱に入れると良いということです。
そのため、まずりんごを重さの昇順にソートします。
ソートすることで、隣接したりんご同士を同じ箱に入れることでばらつきを抑えることができます。

次に、\(N\) 個のりんごを \(K\) 個のグループ（箱）に分けることを考えます。
これは、ソートされたりんごの列を \(K\) 個の連続した区間に分割することに対応します。

ここで重要な観察があります：
- 各箱のばらつき度は、その箱の中での「最大値 - 最小値」です。 - ソート済みの列を区切ってグループを作るとき、各区間の両端の差がばらつき度になります。 - つまり、全体の「隣接差分の合計」から、どこで区切らないか（=連結を保つか）によってコストが変わると考えられます。

したがって、全体の隣接差分の合計から、最も大きな \(K-1\) 個の差分を除けばよいのです。
これらの差分を除くことで、それらの箇所では区切りを作らず、コストが加算されません。

例えば： - りんごの重さが [1, 3, 5, 7, 9]、箱の数 \(K = 3\) の場合、 - 隣接差分は [2, 2, 2, 2]、合計は \(8\) - 最大の \(K-1 = 2\) 個の差（つまり2つ選んでスキップ）を選ぶと、コストは \(8 - 2 - 2 = 4\)

このように、ソートして差分を取る → 大きい方から \(K-1\) 個を除くという方針で最適解が得られます。

アルゴリズム

1. りんごの重さリスト \(A\) を昇順にソートする。
2. 隣接項の差を計算し、リスト diff に格納する（長さ \(N-1\)）。
3. diff を降順にソートする。
4. diff の総和から、上位 \(K-1\) 個の要素の和を引いたものを答えとする。

※ 累積和を使うことで、和の計算を高速に行っています。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(N)\)

実装のポイント

• りんごの重さが最大 \(10^9\) なので、差も32bit整数に収まらない可能性があるため、Pythonのように任意精度整数を使う言語が安心。
• 入力を高速に読み込むために sys.stdin.read を使用している。
• itertools.accumulate を使って累積和を前処理し、和の計算を効率化している。
• \(K = 1\) のときはスキップする要素がないので、例外処理が必要。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))
    
    A.sort()
    
    # 隣接するりんごの重さの差を計算
    diff = [A[i+1] - A[i] for i in range(N-1)]
    
    # 差を降順にソートして、大きい方からK-1個を選ばない（つまり、K-1個のギャップを無視）
    diff.sort(reverse=True)
    
    # 累積和を使って高速に計算
    cumsum = [0] + list(accumulate(diff))
    
    # 全体の差の合計から、選ばないK-1個の差の合計を引く
    total_diff = cumsum[-1]
    skip_sum = sum(diff[:K-1]) if K > 1 else 0
    
    result = total_diff - skip_sum
    print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。