Overview

This problem asks you to find the meeting point that minimizes the total travel distance for \(N\) friends positioned on a number line. The optimal meeting point is at the median position.

Analysis

Key Insight: The Median is Optimal

The value of \(P\) that minimizes the total travel distance \(\sum_{i=1}^{N} |X_i - P|\) is the median of the coordinates.

Why is the Median Optimal?

Let’s consider a concrete example. Suppose friends are located at coordinates \(1, 3, 7\) (\(N=3\)):

• When \(P = 1\): \(|1-1| + |3-1| + |7-1| = 0 + 2 + 6 = 8\)
• When \(P = 3\): \(|1-3| + |3-3| + |7-3| = 2 + 0 + 4 = 6\) ← Minimum!
• When \(P = 7\): \(|1-7| + |3-7| + |7-7| = 6 + 4 + 0 = 10\)

Choosing \(3\), which is the median, gives the minimum.

Intuitive Understanding

If we move the meeting point \(P\) slightly to the right: - All friends to the left of \(P\) will have their travel distance increase - All friends to the right of \(P\) will have their travel distance decrease

In other words, if there are equal numbers of people on both sides of \(P\), moving \(P\) will cause the increases and decreases to cancel out. The median is precisely the position that satisfies this condition.

Problem with the Naive Approach

If we try all integers \(P\) (from \(-10^9\) to \(10^9\)), there are approximately \(2 \times 10^9\) possibilities, which will result in TLE (Time Limit Exceeded). By directly calculating the median, we only need \(O(N \log N)\) time for sorting.

Algorithm

1. Sort the coordinates
2. Find the median
   • If \(N\) is odd: \(X[N/2]\) (the middle element in 0-indexed)
   • If \(N\) is even: \(X[N/2 - 1]\) or \(X[N/2]\) (either is optimal)
3. Calculate the sum of distances from each friend’s coordinate to the median

Additional Note for Even Numbers

When \(N\) is even, any point between the two middle values (inclusive) gives the same total travel distance. When seeking an integer solution, you can choose either of these two points.

Complexity

• Time complexity: \(O(N \log N)\) (sorting is the bottleneck)
• Space complexity: \(O(N)\) (array to store coordinates)

Implementation Notes

• Be careful with indices after sorting. For \(N\) elements in 0-indexed, the median is x[n // 2] (odd) or between x[n // 2 - 1] and x[n // 2] (even)
• Since coordinates range from \(-10^9\) to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total travel distance can be up to approximately \(2 \times 10^{14}\). In Python, there’s no need to worry about integer overflow, but in other languages, you need to use long long type

Source Code

n = int(input())
x = list(map(int, input().split()))
x.sort()

# The total travel distance is minimized when the meeting point is at the median
median = x[n // 2] if n % 2 == 1 else x[n // 2 - 1]

# Calculate the total travel distance
total_distance = sum(abs(xi - median) for xi in x)
print(total_distance)

---

This editorial was generated by claude4.5opus.