概要

本の厚さを並べ替えたとき、隣り合う厚さ差の絶対値和を最小にする値は、実は「最大値 − 最小値」になります。

考察

一見すると「最適な並べ方」を探す問題に見えるため、全探索（\(N!\) 通り）や、DP で順列を扱うような方針を考えがちですが、\(N \le 2\times 10^5\) なので到底間に合いません。

ここで重要な観察は次の2点です。

1. どんな並べ方でも下限は \(M-m\)

厚さの最小値を \(m=\min(V)\)、最大値を \(M=\max(V)\) とします。
どんな順列で並べても、並びの中には必ず \(m\) と \(M\) が登場します。

並びの中で、\(m\) がある位置から \(M\) がある位置までの区間を見ます。この区間の隣接差の和は

\[ |a_{k+1}-a_k| + |a_{k+2}-a_{k+1}| + \cdots + |a_\ell-a_{\ell-1}| \ge |a_\ell-a_k| \]

（絶対値の三角不等式）より、

\[ \ge |M-m| = M-m \]

となります。全体の和はこの区間の和以上なので、どんな並べ方でも答えは必ず \(M-m\) 以上です。

2. 昇順（または降順）に並べればちょうど \(M-m\) になる

厚さを昇順に並べた列を \(b_1 \le b_2 \le \cdots \le b_N\) とすると、

\[ \sum_{i=1}^{N-1} |b_{i+1}-b_i| = \sum_{i=1}^{N-1} (b_{i+1}-b_i) = b_N - b_1 = M - m \]

よって下限 \(M-m\) を達成でき、最小値は \(M-m\) に確定します。

具体例

\(V=[3,10,6]\) のとき \(m=3, M=10\) なので答えは \(7\)。
実際に昇順 \([3,6,10]\) なら \(|6-3|+|10-6|=3+4=7\) で達成できます。

アルゴリズム

1. 配列 \(V\) から最小値 \(m\) と最大値 \(M\) を求める
2. \(M-m\) を出力する
   （\(N=1\) のときも \(M=m\) なので結果は \(0\) になります）

計算量

• 時間計算量: \(O(N)\)（最小・最大を1回ずつ走査して求めるだけ）
• 空間計算量: \(O(1)\)（入力配列以外にほぼ不要）

実装のポイント

• 並べ替え自体は不要で、必要なのは \(\min\) と \(\max\) だけです。

• \(N=1\) の場合は差が \(0\) になる点に注意します（ただし \(\max-\min\) でも自然に \(0\) になります）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    v = data[1:1+n]
    print(max(v) - min(v) if n >= 1 else 0)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。