Overview

A problem where you rearrange the thicknesses of books appropriately to minimize the sum of absolute differences between adjacent books’ thicknesses.

Analysis

In this problem, we want to minimize the sum of absolute differences between adjacent elements: $\( \sum_{i=1}^{N-1} |V_{P(i+1)} - V_{P(i)}| \)\( where \)P$ represents a permutation.

Naively, we could try all possible permutations to find the solution, but since there are \(N!\) permutations, this is not practical when \(N\) becomes large (the time complexity explodes).

A key observation is that “arranging the sequence in sorted order minimizes the sum of differences between adjacent terms.” Intuitively, this is because avoiding alternating large and small values keeps the differences small.

For example, when $\(V = [1, 3, 5]\)\(, arranging in sorted order gives a total difference of: \)\( |3 - 1| + |5 - 3| = 2 + 2 = 4 \)\( while another permutation (e.g., \)\([1, 5, 3]\)\() gives: \)\( |5 - 1| + |3 - 5| = 4 + 2 = 6 \)$ which is a larger value.

Therefore, the optimal arrangement is simply the sorted order, and the answer can be obtained by sorting and then summing the differences between adjacent terms.

Algorithm

1. Read the list of book thicknesses \(V\).
2. Sort the list \(V\) in ascending order.
3. For the sorted list, sum up the differences between adjacent elements (which are always non-negative).
4. Output the total.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• In Python, you can easily sort in ascending order using list.sort() or sorted().

• Since the list is sorted, the difference between adjacent terms is always non-negative when simply subtracted, so abs() is unnecessary.

  Source Code

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)

This editorial was generated by qwen3-coder-480b.