Overview

For each of \(N\) packages, we select the nearest delivery center from \(M\) available centers and minimize the total distance. Since each package can independently choose its nearest delivery center, this can be solved efficiently using binary search.

Analysis

Key Insight: Each package can independently choose its optimal delivery center

The value we want to minimize is \(\sum_{i=1}^{N} |D_i - S_{f(i)}|\). Looking carefully at this expression, the term \(|D_i - S_{f(i)}|\) for each package \(i\) is not affected at all by the assignments of other packages (since one delivery center can handle multiple packages). Therefore, we simply need to choose the nearest delivery center for each package individually.

Problem with the Naive Approach

If we check all delivery centers \(j\) for each package \(i\) to find the minimum of \(|D_i - S_j|\), the time complexity is \(O(N \times M)\). When both \(N\) and \(M\) can be up to \(2 \times 10^5\), this requires \(4 \times 10^{10}\) computations, which will not fit within the time limit (TLE).

Solution: Sort + Binary Search

If we sort the delivery center coordinates in advance, we can find the nearest delivery center to each destination \(D_i\) in \(O(\log M)\) using binary search.

Let’s explain with a concrete example. Suppose the delivery centers are \(S = [1, 5, 8]\) (sorted) and the destination is \(D_i = 6\):

• Binary search finds the insertion position of \(6\) as \(\text{pos} = 2\) (\(S[2] = 8\) is the smallest element \(\geq 6\))
• Right candidate: \(S[2] = 8\) → distance \(|6 - 8| = 2\)
• Left candidate: \(S[1] = 5\) → distance \(|6 - 5| = 1\)
• The minimum is \(1\), so we choose delivery center \(5\)

Algorithm

1. Sort the delivery center coordinates \(S\).
2. For each package’s destination \(D_i\), do the following:
   • Use bisect_left to find the insertion position \(\text{pos}\) of \(D_i\) in the sorted array \(S\).
   • The two nearest candidates are \(S[\text{pos}]\) (the smallest value \(\geq D_i\)) and \(S[\text{pos}-1]\) (the largest value \(< D_i\)).
   • After performing boundary checks (when \(\text{pos} = 0\) or \(\text{pos} = M\)), choose the candidate with the smaller distance.
3. Sum up the minimum distances for all packages and output the result.

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  • \(O(M \log M)\) for sorting the delivery centers, and \(O(\log M)\) × \(N\) times for binary search on each package
• Space complexity: \(O(N + M)\)
  • Required for storing the input data

Implementation Notes

• Boundary checks are important: When the insertion position \(\text{pos}\) obtained from binary search is \(0\), there is no left candidate, and when it is \(M\), there is no right candidate. Both cases must be handled correctly.

• Fast I/O: Since \(N\) and \(M\) can be large, in Python we speed up input by reading everything at once with sys.stdin.buffer.read().

• Efficient distance calculation: Since \(S\) is sorted, we have \(S[\text{pos}] \geq D_i\) and \(S[\text{pos}-1] < D_i\). Therefore, instead of taking absolute values, we can compute distances as S[pos] - d and d - S[pos-1], which is slightly more efficient.

  Source Code

import bisect
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    D = [int(input_data[idx + i]) for i in range(N)]; idx += N
    S = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    S.sort()
    
    total = 0
    for d in D:
        pos = bisect.bisect_left(S, d)
        best = float('inf')
        if pos < M:
            best = min(best, S[pos] - d)
        if pos > 0:
            best = min(best, d - S[pos - 1])
        total += best
    
    print(total)

main()

This editorial was generated by claude4.6opus-thinking.