Overview

Given \(N\) points \(X_i\) on a number line, this problem asks us to minimize the total distance from some point \(P\) to all points: \(\sum_{i=1}^{N} |X_i - P|\). This is a classic problem known in statistics and mathematics as “L1 norm minimization.”

Analysis

The key to solving this problem is recognizing the property that “the point \(P\) that minimizes the sum of absolute values is the median of the given coordinates.”

Why the Median?

To build intuitive understanding, let’s consider how the total travel distance changes as we move the meeting point \(P\).

1. Suppose there are \(L\) friends to the left of \(P\) and \(R\) friends to the right of \(P\).
2. If we move \(P\) slightly to the right by a distance \(d\):
   • The travel distance for each of the \(L\) people on the left increases by \(d\) (total \(+L \times d\)).
   • The travel distance for each of the \(R\) people on the right decreases by \(d\) (total \(-R \times d\)).
   • The overall change is \((L - R) \times d\).

From this expression, we can see: - If \(L < R\) (more people on the right), moving right decreases the total distance. - If \(L > R\) (more people on the left), moving left decreases the total distance. - When \(L = R\) (equal number of people on both sides), the total distance stops changing and reaches its minimum.

In other words, the point where the number of people on the left and right is balanced — namely the median — is the optimal \(P\).

Even Case

When \(N\) is even, there are two middle values (\(X_{N/2}\) and \(X_{N/2 + 1}\)), but choosing any point (integer) between them as \(P\) results in the same total travel distance, since the number of people on both sides remains equal. Therefore, in implementation, it suffices to simply choose the middle element of the sorted list as \(P\).

Algorithm

1. Sort the given \(N\) coordinates \(X_1, X_2, \ldots, X_N\) in ascending order.
2. In the sorted array, take the element at the middle position as \(P\) (e.g., X[N // 2]).
3. For each \(X_i\), compute \(|X_i - P|\) and sum them up.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the coordinates takes \(O(N \log N)\).
  • Computing the sum of distances takes \(O(N)\).
  • Overall, sorting is the dominant operation.
• Space complexity: \(O(N)\)
  • An array of length \(N\) is needed to store the input coordinates.

Implementation Notes

• Importance of sorting: Sorting must be performed first to correctly obtain the median.

• Handling large values: Since \(X_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total travel distance can be approximately \(2 \times 10^{14}\). In Python, there is no limit on integer size, but when using other languages (such as C++), you need to use a 64-bit integer type (such as long long).

  Source Code

import sys

def solve():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nの取得
    n = int(input_data[0])
    # X_iのリストを取得
    x = [int(val) for val in input_data[1:]]
    
    # 座標をソートする
    x.sort()
    
    # 総移動距離を最小にするPは中央値である。
    # Nが奇数の場合は中央の要素、偶数の場合は中央の2つの要素の間の任意の整数がPとなる。
    # ここでは x[n // 2] をPとして選択する。
    p = x[n // 2]
    
    # 各友人からの移動距離の合計を計算
    ans = 0
    for xi in x:
        ans += abs(xi - p)
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.