Overview

When you can process the reagent temperatures \(H_i\) in any order you like, find the minimum travel cost (sum of absolute differences in temperature) to visit all temperatures starting from temperature \(0\) and returning to \(0\) at the end.

Analysis

Key Insight: Only the “endpoints (minimum and maximum)” matter

Temperatures can be viewed as points on a number line, and cost is the travel distance (absolute difference). In this case, all reagent temperatures lie within the interval \([\min H, \max H]\).

• “Intermediate points” in the interval can be processed along the way while moving from one end to the other (no additional detour cost).
• Therefore, the minimum cost is determined solely by the minimum and maximum temperatures that must be reached (plus the starting point 0).

Specifically, including 0 in the range to be covered, let: - Left endpoint \(L=\min(0,\min H)\) - Right endpoint \(R=\max(0,\max H)\)

Then what we need is to cover the interval \([L,R]\).

Why a naive approach doesn’t work

Since the order is freely chosen, trying all permutations gives \(N!\) possibilities, which is clearly infeasible (\(N\le 2\times 10^5\)). Even considering DP approaches like TSP, \(N\) is far too large.

Lower bound on the minimum cost (it cannot be made smaller than this)

Let the temperature sequence for any processing order be \(x_0=0,x_1,\dots,x_N,x_{N+1}=0\). Let the maximum of this sequence be \(M=\max x_i\) and the minimum be \(m=\min x_i\). On the number line:

• Going up from \(m\) to \(M\) requires at least \(M-m\) of upward movement
• Then returning to 0 requires at least \(M-m\) of downward movement

Therefore, the total travel distance (cost) always satisfies [ \sum |xi-x{i-1}| \ge 2(M-m) ]

Furthermore, to process all reagents, we must visit at least the range \(L\) to \(R\), so \(M\ge R,\ m\le L\), which gives \(M-m\ge R-L\). Therefore [ \text{Cost} \ge 2(R-L) ] always holds.

This lower bound is achievable (i.e., it is optimal)

For example, we can move as follows:

• Go from 0 to the left endpoint \(L\) (processing reagents along the way)
• Move straight from \(L\) to the right endpoint \(R\) (processing reagents along the way)
• Return from \(R\) to 0

The cost in this case is [ |0-L| + |R-L| + |R-0| = (-L) + (R-L) + R = 2(R-L) ] which matches the lower bound, so it is optimal.

Example: For \(H=[-5,-2,3,4]\), we have \(L=-5,\ R=4\) 0 → -5 → 4 → 0 gives cost \(5+9+4=18 = 2(4-(-5))\). The intermediate values -2 and 3 are processed along the way.

Algorithm

1. Compute \(mn=\min(H)\), \(mx=\max(H)\)
2. Calculate \(L=\min(0,mn)\), \(R=\max(0,mx)\)
3. Output the answer \(2(R-L)\)

This corresponds to the following in the code: - mn = min(H) - mx = max(H) - ans = 2 * (max(0, mx) - min(0, mn))

Complexity

• Time complexity: \(O(N)\) (one scan each for minimum and maximum)
• Space complexity: \(O(1)\) (constant aside from the input array)

Implementation Notes

• The cases where all values are positive, all are negative, or both positive and negative are mixed are handled uniformly by \(L=\min(0,mn),\ R=\max(0,mx)\)

• \(H_i\) can be up to \(\pm 10^9\) and \(N\) can be large, but since Python integers do not overflow, this is handled without issues

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.