/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は配送会社で働いています。今日は N 個の荷物をそれぞれ指定された届け先に届ける必要があります。第 i 個の荷物の届け先は、数直線上の座標 D_i にあります。
この配送会社には M 箇所の配送センターがあり、第 j 番目の配送センターは数直線上の座標 S_j に位置しています。各荷物はいずれか 1 つの配送センターから出発して届け先へ運ばれます。配送センター j から荷物 i の届け先まで運ぶコストは、距離 |D_i - S_j| です。
各荷物はちょうど 1 つの配送センターに割り当てなければなりません。ただし、1 つの配送センターが複数の荷物を担当することも、どの荷物も担当しない配送センターがあることも許されます。
すべての荷物の配送コストの合計を最小化してください。
すなわち、各荷物 i （ 1 \leq i \leq N ）に対して配送センター f(i) （ 1 \leq f(i) \leq M ）を割り当てたとき、
\sum_{i=1}^{N} |D_i - S_{f(i)}|
の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- -10^9 \leq D_i \leq 10^9 （ 1 \leq i \leq N ）
- -10^9 \leq S_j \leq 10^9 （ 1 \leq j \leq M ）
- 入力はすべて整数である。
入力
N M D_1 D_2 \ldots D_N S_1 S_2 \ldots S_M
- 1 行目には、荷物の個数を表す N と、配送センターの数を表す M が、スペース区切りで与えられる。
- 2 行目には、各荷物の届け先の座標を表す D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
- 3 行目には、各配送センターの座標を表す S_1, S_2, \ldots, S_M が、スペース区切りで与えられる。
出力
配送コストの合計の最小値を 1 行で出力せよ。
入力例 1
3 2 1 4 7 3 6
出力例 1
4
入力例 2
5 3 -10 -3 0 5 15 -7 2 12
出力例 2
15
入力例 3
10 4 -100 -50 -20 0 10 30 60 80 200 500 -40 15 70 450
出力例 3
325
Score : 333 pts
Problem Statement
Takahashi works at a delivery company. Today, he needs to deliver N packages to their designated destinations. The destination of the i-th package is at coordinate D_i on a number line.
This delivery company has M distribution centers, and the j-th distribution center is located at coordinate S_j on the number line. Each package departs from exactly one distribution center and is transported to its destination. The cost of transporting package i from distribution center j to its destination is the distance |D_i - S_j|.
Each package must be assigned to exactly one distribution center. However, a single distribution center may handle multiple packages, and there may be distribution centers that handle no packages at all.
Minimize the total delivery cost of all packages.
That is, when assigning a distribution center f(i) (1 \leq f(i) \leq M) to each package i (1 \leq i \leq N), find the minimum value of
\sum_{i=1}^{N} |D_i - S_{f(i)}|
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- -10^9 \leq D_i \leq 10^9 (1 \leq i \leq N)
- -10^9 \leq S_j \leq 10^9 (1 \leq j \leq M)
- All input values are integers.
Input
N M D_1 D_2 \ldots D_N S_1 S_2 \ldots S_M
- The first line contains N, the number of packages, and M, the number of distribution centers, separated by a space.
- The second line contains D_1, D_2, \ldots, D_N, the coordinates of each package's destination, separated by spaces.
- The third line contains S_1, S_2, \ldots, S_M, the coordinates of each distribution center, separated by spaces.
Output
Print the minimum total delivery cost on a single line.
Sample Input 1
3 2 1 4 7 3 6
Sample Output 1
4
Sample Input 2
5 3 -10 -3 0 5 15 -7 2 12
Sample Output 2
15
Sample Input 3
10 4 -100 -50 -20 0 10 30 60 80 200 500 -40 15 70 450
Sample Output 3
325