概要

試薬の温度 \(H_i\) を好きな順に処理できるとき、開始温度 \(0\) から全ての温度を訪れて最後に \(0\) に戻るまでの移動コスト（温度差の絶対値の総和）の最小値を求めます。

考察

重要な気づき：必要なのは「両端（最小値・最大値）」だけ

温度は数直線上の点とみなせ、コストは移動距離（絶対値差）です。
このとき、全ての試薬の温度は区間 \([\min H, \max H]\) の中にあります。

• 区間の「途中の点」は、端から端へ移動する途中でついでに処理できます（寄り道コストが増えない）。
• したがって、最小コストを決めるのは 到達すべき最小温度と最大温度（＋開始点 0） だけです。

具体的には、0 も含めた到達範囲を - 左端 \(L=\min(0,\min H)\) - 右端 \(R=\max(0,\max H)\)
とすると、必要なのは区間 \([L,R]\) をカバーすることです。

素朴な方法がダメな理由

順番を自由に選べるので、全順列を試すと \(N!\) 通りで当然無理です（\(N\le 2\times 10^5\)）。
また TSP のような DP を考えても \(N\) が大きすぎて不可能です。

最小コストの下界（これ以上小さくできない）

任意の処理順での温度列を \(x_0=0,x_1,\dots,x_N,x_{N+1}=0\) とします。
この列の最大値を \(M=\max x_i\)、最小値を \(m=\min x_i\) とすると、数直線上で

• \(m\) から \(M\) へ上がるには少なくとも \(M-m\) の上昇が必要
• その後 0 に戻るまでに少なくとも \(M-m\) の下降が必要

よって、総移動量（コスト）は必ず [ \sum |xi-x{i-1}| \ge 2(M-m) ] となります。

さらに、全試薬を処理するには少なくとも \(L\) と \(R\) の範囲を訪れる必要があるので
\(M\ge R,\ m\le L\) より \(M-m\ge R-L\)。したがって [ \text{コスト} \ge 2(R-L) ] が必ず成り立ちます。

この下界は達成できる（つまり最適）

例えば次のように動けばよいです。

• 0 → 左端 \(L\) まで行く（途中の試薬も処理）
• \(L\) → 右端 \(R\) まで一直線に移動（途中の試薬も処理）
• \(R\) → 0 に戻る

このときコストは [ |0-L| + |R-L| + |R-0| = (-L) + (R-L) + R = 2(R-L) ] となり、下界と一致するため最小です。

例：\(H=[-5,-2,3,4]\) のとき \(L=-5,\ R=4\)
0 → -5 → 4 → 0 でコスト \(5+9+4=18 = 2(4-(-5))\)。途中で -2 や 3 はついでに処理できます。

アルゴリズム

1. \(mn=\min(H)\)、\(mx=\max(H)\) を求める
2. \(L=\min(0,mn)\)、\(R=\max(0,mx)\) を計算
3. 答えは \(2(R-L)\) を出力

これはコード中の - mn = min(H) - mx = max(H) - ans = 2 * (max(0, mx) - min(0, mn)) に対応します。

計算量

• 時間計算量: \(O(N)\)（最小値・最大値を1回ずつ走査）
• 空間計算量: \(O(1)\)（入力配列を除けば定数）

実装のポイント

• 全て正の場合・全て負の場合・両方混在の場合を、\(L=\min(0,mn),\ R=\max(0,mx)\) で統一して扱える

• \(H_i\) は最大で \(\pm 10^9\)、\(N\) も大きいですが、Python の整数はオーバーフローしないのでそのままでOKです

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    H = list(map(int, input().split()))
    mn = min(H)
    mx = max(H)
    ans = 2 * (max(0, mx) - min(0, mn))
    print(ans)

if __name__ == "__main__":
    main()

---

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