Overview

A problem where packages on a number line are delivered from the nearest delivery center to minimize the total cost.

Analysis

This is a problem of choosing “which delivery center to send from” for each package, where the cost is simply the distance \(|D_i - S_j|\) between the “package position” and the “delivery center position”.

A naive approach would be to calculate the distance from each package to every delivery center and choose the minimum. However, this requires \(M\) comparisons per package, resulting in an overall time complexity of \(O(NM)\). Given the constraints \(N, M \leq 2 \times 10^5\), this would require up to \(4 \times 10^{10}\) computations, which would TLE.

Here is a key observation:

On a number line, the closest point to a given point is one of the two adjacent points in a sorted list.

In other words, if we sort the delivery center coordinates, we can efficiently find the nearest delivery center for each package using binary search. Since there are at most 2 candidates (the element at the insertion position and the one before it), we can significantly reduce the computation.

Algorithm

1. Sort the list of delivery center coordinates \(S\).
2. For each package coordinate \(D_i\), do the following:
   • Use bisect.bisect_left(S, D_i) to obtain the insertion position pos of \(D_i\).
   • Among S[pos] and S[pos - 1] (if they exist), choose the closer one and add the cost.
3. Output the sum of costs for all packages.

Example

Package positions: \(D = [1, 5]\)
Delivery center positions: \(S = [2, 8, 3]\)

1. After sorting: \(S = [2, 3, 8]\)
2. \(D_1 = 1\): The nearest is \(S_1 = 2\) → Cost \(|1 - 2| = 1\)
3. \(D_2 = 5\): The nearest is \(S_2 = 3\) → Cost \(|5 - 3| = 2\)
4. Total cost: \(1 + 2 = 3\)

Complexity

• Time complexity: \(O((N + M)\log M)\)
  • \(O(M \log M)\) for sorting, \(O(N \log M)\) for binary search and candidate checking per package
• Space complexity: \(O(M)\)
  • For storing the sorted list of delivery centers

Implementation Notes

• The list of delivery centers must be sorted in advance.
• Be careful to avoid index errors when the result pos of bisect.bisect_left() is at the boundary of the list (0 or M).
• For each package, you only need to check at most 2 candidates (the elements before and after the insertion point).

## Source Code

```python
import bisect
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    D = list(map(int, data[2:2+N]))
    S = list(map(int, data[2+N:2+N+M]))
    
    # 配送センターの座標をソート
    S.sort()
    
    total_cost = 0
    for d in D:
        # 二分探索で最も近い配送センターを見つける
        pos = bisect.bisect_left(S, d)
        min_dist = float('inf')
        
        # 候補は最大2つ（pos-1 と pos）
        if pos < M:
            min_dist = min(min_dist, abs(d - S[pos]))
        if pos > 0:
            min_dist = min(min_dist, abs(d - S[pos - 1]))
            
        total_cost += min_dist
        
    print(total_cost)

if __name__ == "__main__":
    main()

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