Overview

Each package should be sent from the “nearest delivery center,” and the problem asks to minimize the total distance across all packages. We sort the delivery centers and use binary search to find the nearest center for each package’s position.

Analysis

Key Insight

In this problem, “any delivery center can handle any number of packages,” so the assignments of packages do not affect each other.
In other words, to minimize the total cost $\(\sum_{i=1}^{N} |D_i - S_{f(i)}|\)\( it suffices to **independently** choose for each package \)i\( the delivery center \)j\( that minimizes \)|D_i - S_j|$ (since other packages’ choices do not impose any additional constraints).

Why the Naive Solution Is Too Slow

If we check all delivery centers \(S_j\) for each package \(D_i\) to find the minimum distance, the time complexity becomes \(O(NM)\).
At maximum, this is \(2\times10^5 \times 2\times10^5 = 4\times10^{10}\), which will not finish in time (TLE).

How to Solve It

If we sort the delivery center coordinates \(S\) in advance, the nearest center to a package position \(x\) is one of the following in the sorted array: - The first element that is \(\ge x\) (right candidate) - The element immediately to its left (left candidate)

For example, if \(S=[0, 10, 20]\) and \(x=13\), the insertion position is between \(10\) and \(20\), so the only candidates are \(10\) and \(20\). Thus, we can find the candidates using binary search and compare them.

Algorithm

1. Sort the delivery center coordinate array \(S\) in ascending order.
2. For each package destination \(x (=D_i)\), do the following:
   • Use bisect_left(S, x) to find pos, the leftmost position where \(x\) can be inserted in \(S\) (the smallest pos such that \(S[pos]\ge x\)).
   • There are at most 2 candidates:
     • Right candidate: if pos < M, the distance is \(|x - S[pos]|\)
     • Left candidate: if pos > 0, the distance is \(|x - S[pos-1]|\)
   • Add the smaller of the two distances as the minimum cost for that package.
3. Output the accumulated result.

This method efficiently finds the nearest center for each package.

Complexity

• Time complexity: \(O(M\log M + N\log M)\) (sorting + binary search for each package)
• Space complexity: \(O(M)\) (storing the delivery center array)

Implementation Notes

• The value pos returned by bisect_left can range from \(0\) to \(M\), so you must handle the boundary cases where pos==0 (no left candidate) or pos==M (no right candidate) with proper branching.

• Distances are computed using the absolute value abs(...).

• Since the input can be up to \(2\times10^5\), in Python using sys.stdin.buffer.read() allows for faster input reading.

  Source Code

import sys
from bisect import bisect_left

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    D = [next(it) for _ in range(N)]
    S = [next(it) for _ in range(M)]
    S.sort()

    ans = 0
    for x in D:
        pos = bisect_left(S, x)
        best = 10**30
        if pos < M:
            best = abs(x - S[pos])
        if pos > 0:
            d = abs(x - S[pos - 1])
            if d < best:
                best = d
        ans += best

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.