概要

数直線上の荷物を、最も近い配送センターから配送することで、総コストを最小にする問題。

考察

各荷物を「どの配送センターから送るか」を選ぶ問題ですが、コストは単純に「荷物の位置」と「配送センターの位置」の距離 \(|D_i - S_j|\) です。

素朴な方法として、各荷物についてすべての配送センターとの距離を計算し、最小のものを選ぶ方法があります。しかし、これは各荷物に対し \(M\) 回の比較が必要なので、全体で \(O(NM)\) の計算量となり、制約 \(N, M \leq 2 \times 10^5\) では最大で \(4 \times 10^{10}\) 回の計算が必要になり、TLEします。

そこで重要な観察があります：

数直線上では、ある点に最も近い点は、ソートされたリストにおいてその点の前後にあるいずれかである。

つまり、配送センターの座標をソートしておけば、各荷物に対して二分探索により最も近い配送センターを効率的に求めることができます。候補は多くても2つ（挿入位置とその前の要素）なので、計算量を大幅に削減できます。

アルゴリズム

1. 配送センターの座標リスト \(S\) をソートする。
2. 各荷物の座標 \(D_i\) に対して以下を行う：
   • bisect.bisect_left(S, D_i) を使い、\(D_i\) の挿入位置 pos を得る。
   • S[pos] および S[pos - 1]（存在すれば）のうち、より近い方を選んでコストに加える。
3. 全荷物のコストを合計したものを出力する。

例

荷物の位置: \(D = [1, 5]\)
配送センターの位置: \(S = [2, 8, 3]\)

1. ソートして \(S = [2, 3, 8]\)
2. \(D_1 = 1\): 最も近いのは \(S_1 = 2\) → コスト \(|1 - 2| = 1\)
3. \(D_2 = 5\): 最も近いのは \(S_2 = 3\) → コスト \(|5 - 3| = 2\)
4. 合計コスト: \(1 + 2 = 3\)

計算量

• 時間計算量: \(O((N + M)\log M)\)
  • ソートに \(O(M \log M)\)、各荷物に対する二分探索と候補チェックに \(O(N \log M)\)
• 空間計算量: \(O(M)\)
  • 配送センターのリストをソートして保持するため

実装のポイント

• 配送センターのリストは事前にソートしておくこと。
• bisect.bisect_left() の結果 pos がリストの端（0またはM）にある場合に、インデックスエラーにならないよう注意。
• 各荷物に対して候補は最大2つ（前後の要素）だけ確認すればよい。

## ソースコード

```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()

この解説は qwen3-coder-480b によって生成されました。