Overview

This is a problem where you need to choose a meeting place that minimizes the total travel distance for all \(N\) friends on a number line, and compute the sum of those distances.

Analysis

The key to this problem is deciding where to place the meeting point \(P\). The goal is to find the value of \(P\) that minimizes $\( \sum_{i=1}^{N} |X_i - P| \)$

This is a classic “minimizing the sum of absolute values” problem, and it has a well-known mathematical property:

For a set of points on a number line, the point that minimizes the sum of absolute distances from all points is the median.

For example, suppose friends are at coordinates \([1, 2, 4]\). Let’s try a few candidate meeting places:

• \(P = 1\): \(|1-1| + |2-1| + |4-1| = 0 + 1 + 3 = 4\)
• \(P = 2\): \(|1-2| + |2-2| + |4-2| = 1 + 0 + 2 = 3\)
• \(P = 3\): \(|1-3| + |2-3| + |4-3| = 2 + 1 + 1 = 4\)

The smallest value is at \(P = 2\) (i.e., the median).

However, we need to be careful when the number of elements is even. For example, with \([1, 2, 4, 5]\), the optimal solution is any value between the two middle values. In this case, choosing \(P = 2\), \(3\), or \(4\) all give the same result.

Therefore, if \(N\) is odd, we pick the middle value; if \(N\) is even, we can pick either of the two middle values (left or right) to obtain the optimal solution.

A naive approach of trying all possible values of \(P\) via brute force is conceivable, but since there can be up to \(2 \times 10^5\) friends, this is computationally infeasible (time complexity \(O(N \cdot (\max(X)-\min(X)))\)). Additionally, coordinates can be negative, making the handling more cumbersome.

Instead, we use the technique of “sorting and using the median.” This allows us to efficiently find the optimal meeting place.

Algorithm

1. Sort the list of friend coordinates \(X\) in ascending order.
2. Find the median of the sorted list:
   • If \(N\) is odd: \(X[N//2]\)
   • If \(N\) is even: \(X[N//2 - 1]\) (either works, but we use the left one for convenience)
3. Using the median as the meeting place \(P\), sum up the absolute differences \(|X_i - P|\) for each \(X_i\) to compute the total travel distance.
4. Output the result.

Complexity

• Time complexity: \(O(N \log N)\) (mainly due to the overhead of sorting)
• Space complexity: \(O(1)\) (constant memory excluding the input)

Implementation Notes

• In Python, you can easily sort using list.sort() or the sorted() function.

• Understanding that the result does not change regardless of which middle value you choose for even-length cases helps avoid confusion.

• To efficiently compute the sum of absolute values, there is no need to consider any choice other than the median.

  Source Code

N = int(input())
X = list(map(int, input().split()))

X.sort()

if N % 2 == 1:
    median = X[N // 2]
else:
    median = X[N // 2 - 1]

total_distance = sum(abs(x - median) for x in X)

print(total_distance)

---

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