概要

各荷物を「最も近い配送センター」から送ればよく、全荷物についてその距離の合計を最小化する問題です。配送センターをソートし、各荷物の位置に最も近いセンターを二分探索で求めます。

考察

重要な気づき

この問題では「どの配送センターが何個の荷物を担当してもよい」ため、荷物同士の割り当てが互いに影響しません。
つまり、合計コスト $\(\sum_{i=1}^{N} |D_i - S_{f(i)}|\)\( を最小にするには、各荷物 \)i\( について **個別に** \)|D_i - S_j|\( が最小となる配送センター \)j$ を選べば十分です（他の荷物の選択によって制約が増えないため）。

素朴解がなぜ遅いか

各荷物 \(D_i\) について全配送センター \(S_j\) を調べて最小距離を取ると、計算量は \(O(NM)\) になります。
最大で \(2\times10^5 \times 2\times10^5 = 4\times10^{10}\) となり、時間内に終わりません（TLE）。

どう解決するか

配送センター座標 \(S\) をソートしておくと、ある荷物位置 \(x\) に最も近いセンターは、ソート配列内で - \(x\) 以上で最初の要素（右側候補） - その1つ左の要素（左側候補） のどちらかになります。

たとえば \(S=[0, 10, 20]\)、\(x=13\) のとき、挿入位置は \(10\) と \(20\) の間なので候補は \(10\) と \(20\) の2つだけです。よって二分探索で候補を見つけて比較すればよいです。

アルゴリズム

1. 配送センターの座標配列 \(S\) を昇順にソートする。
2. 各荷物の届け先 \(x (=D_i)\) について以下を行う：
   • bisect_left(S, x) で、\(S\) の中で \(x\) を挿入できる最左位置 pos を求める（\(S[pos]\ge x\) となる最小の pos）。
   • 候補は最大2つ：
     • 右側候補：pos < M なら距離 \(|x - S[pos]|\)
     • 左側候補：pos > 0 なら距離 \(|x - S[pos-1]|\)
   • 2つの距離の小さい方をその荷物の最小コストとして加算する。
3. 加算結果を出力する。

この方法で、各荷物の最寄りセンターが高速に求まります。

計算量

• 時間計算量: \(O(M\log M + N\log M)\)（ソート + 各荷物の二分探索）
• 空間計算量: \(O(M)\)（配送センター配列の保持）

実装のポイント

• bisect_left の返す pos は \(0\) 〜 \(M\) の範囲を取りうるため、pos==0（左候補なし）や pos==M（右候補なし）の境界ケースを必ず分岐して処理します。

• 距離は絶対値 abs(...) で計算します。

• 入力が最大 \(2\times10^5\) なので、Python では sys.stdin.buffer.read() を使うと高速に読み取れます。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。