Overview

Given the destinations of packages and the positions of delivery centers, the problem asks to minimize the total delivery cost of all packages.

Analysis

A naive approach of trying all delivery centers for each package would result in \(O(N \times M)\) time complexity, which under the constraints (\(N, M \leq 2 \times 10^5\)) would require up to 4 billion computations, exceeding the time limit. An efficient solution is needed.

A key observation is that in an optimal assignment, each package should be delivered from the nearest delivery center. However, finding the nearest neighbor for all combinations of packages and delivery centers is too computationally expensive. Instead, by sorting both the delivery centers and package destinations and scanning through both in order, we can efficiently find the nearest neighbor.

Algorithm

1. Sort the delivery center coordinates \(S\) and package destinations \(D\) respectively.
2. Initialize the delivery center index \(j\) to 0.
3. For each package \(d\) (sorted), compare the current delivery center \(S_j\) with the next delivery center \(S_{j+1}\):
   • If \(|d - S_j| \geq |d - S_{j+1}|\), the next delivery center is closer, so increment \(j\) (as long as \(j < m-1\)).
   • Continue advancing \(j\) until this condition is no longer satisfied, ultimately finding the nearest delivery center \(S_j\).
4. Add the distance from each package to its nearest delivery center to the total.

With this approach, we scan through the list of delivery centers only once while efficiently finding the nearest delivery center for each package.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting takes \(O(N \log N)\) and \(O(M \log M)\), and the scan takes \(O(N + M)\).
• Space complexity: \(O(N + M)\)
  • Memory for storing arrays \(D\) and \(S\).

Implementation Notes

• Sorting both delivery centers and packages enables efficient scanning.

• The delivery center index \(j\) is maintained without resetting. This is because we can leverage the positional relationship between sorted delivery centers and packages, starting the search from the nearest delivery center index found for the previous package.

• The condition abs(d - S[j]) >= abs(d - S[j+1]) evaluates to true when the next delivery center is closer than or equally distant as the current one. Including equality means we advance to the next center when distances are the same (the cost is identical either way, but this maintains consistency in the traversal direction).

  Source Code

import sys

def main():
    data = sys.stdin.read().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()
    D.sort()
    
    total = 0
    j = 0
    for d in D:
        while j < m - 1 and abs(d - S[j]) >= abs(d - S[j+1]):
            j += 1
        total += abs(d - S[j])
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.