Overview

Given positions \(X_i\) of \(N\) people on a number line, we choose a single meeting point \(P\) (an integer) to minimize the total travel distance \(\sum_{i=1}^{N} |X_i - P|\). The conclusion is that the optimal \(P\) is the median.

Analysis

Key Insight (The Median is Optimal)

The total travel distance \(f(P)=\sum |X_i-P|\) has the property that when \(P\) is moved to the right, “the distances for people on the left increase, and the distances for people on the right decrease.”

Intuitively, when \(P\) is shifted slightly to the right: - Let \(L\) be the number of people to the left of \(P\) - Let \(R\) be the number of people to the right of \(P\)

Then the change in distance is roughly: - People on the left: total change of \(+L\) - People on the right: total change of \(-R\)

So the net change is \(L-R\).

In other words: - If \(L < R\), moving right decreases the total distance (it’s still better to shift right) - If \(L > R\), moving right increases the total distance (it’s better to shift back left) - The minimum occurs around the point where \(L = R\)

This “point where the number of people on the left and right is balanced” is the median. Therefore, we should choose the middle element when \(X_i\) is sorted (when \(N\) is even, any point between the two central elements is optimal; under the integer constraint, choosing either of the two central values gives the minimum).

Why a Naive Approach Doesn’t Work

\(P\) can be any integer in a range as wide as \([-10^9,10^9]\), so trying all possible \(P\) values is impossible. Even if we restrict candidates to only the \(X_i\) values, computing the total for each candidate takes \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).

By using the median property, we can determine the optimal point in one shot without any search.

Concrete Example

For example, when \(X=[1,2,10]\), the median is \(2\). - \(P=2\): total distance is \(|1-2|+|2-2|+|10-2|=1+0+8=9\) - \(P=1\): \(0+1+9=10\) - \(P=3\): \(2+1+7=10\)

Indeed, the minimum occurs at the median.

Algorithm

1. Sort the array \(X\) in ascending order.
2. Choose the middle element \(X_{\lfloor N/2 \rfloor}\) as the median (0-indexed).
3. Compute and output \(\sum |X_i - \text{median}|\).

When \(N\) is even, the minimum total distance is achieved for any point “between the two central elements,” but since \(P\) must be an integer in this problem, choosing \(X_{N/2}\) (or \(X_{N/2-1}\)) after sorting gives the minimum value. In the code, we use \(X_{N//2}\).

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the coordinate array)

Implementation Notes

• Since \(N\) can be large, using sys.stdin.buffer.read() for input is faster.

• The sum of coordinates and distances can be as large as \(N \times 2\times 10^9\), but Python’s integers have arbitrary precision, so there is no concern about overflow.

• After obtaining the median, simply computing sum(abs(x - median) for x in xs) works fine.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    xs = list(map(int, data[1:1+n]))
    xs.sort()
    median = xs[n // 2]
    ans = sum(abs(x - median) for x in xs)
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.