概要

本の厚さを適切に並び替えて、隣り合う本の厚さの差の絶対値の総和を最小にする問題。

考察

この問題では、隣り合う要素の差の絶対値の合計 $\( \sum_{i=1}^{N-1} |V_{P(i+1)} - V_{P(i)}| \)\( を最小にしたいです。ここで \)P$ は並び替えを表します。

素朴には、すべての並び替えを試すことで解を求められますが、これは \(N!\) 通りあるため、\(N\) が大きくなると現実的ではありません（時間計算量が爆発する）。

重要な観察として、「数列をソートした順番で並べると、隣接項の差の合計が最小になる」という性質があります。これは直感的にも、大小が交互にならないようにすることで差を小さくできるということです。

たとえば、$\(V = [1, 3, 5]\)\( のとき、ソート済みの順番で並べると差の合計は： \)\( |3 - 1| + |5 - 3| = 2 + 2 = 4 \)\( となり、他の並び替え（例：\)\([1, 5, 3]\)\(）だと： \)\( |5 - 1| + |3 - 5| = 4 + 2 = 6 \)$ となって、より大きな値になります。

したがって、最適な並びはソートされた順番そのものであり、ソート後に隣接項の差を足し合わせるだけで答えが得られます。

アルゴリズム

1. 本の厚さのリスト \(V\) を読み込む。
2. リスト \(V\) を昇順にソートする。
3. ソート後のリストに対し、隣接する要素の差（常に非負）を足し合わせる。
4. 合計値を出力する。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(1)\) （入力配列を除く）

実装のポイント

• Pythonでは list.sort() または sorted() を使うと簡単に昇順ソートできる。

• 隣接項の差は、ソートされているため単純に引き算すれば非負になるので、abs() は不要。

  ソースコード

n = int(input())
v = list(map(int, input().split()))

v.sort()

ans = 0
for i in range(n - 1):
    ans += v[i + 1] - v[i]

print(ans)

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