分数: 333 分
问题陈述
高桥在一家快递公司工作。今天,他需要交付 N 包裹到指定目的地。的目的地 i-第一个包裹位于坐标处 数轴上的 D_i 。
该快递公司有 M 配送中心,以及 j第一个配送中心位于坐标 数轴上的 S_j 。每个包裹均从一个配送中心出发并运输至目的地。运输包裹的费用 i 来自配送中心 j 到目的地的距离 |D_i - S_j|.
每个包裹必须分配到一个配送中心。然而,单个配送中心可以处理多个包裹,并且可能存在根本不处理包裹的配送中心。
最小化所有包裹的总运输成本。
即分配配送中心时 f(i) (1 \leq f(i) \leq M) 到每个包裹 i (1 \leq i \leq N),找到最小值
\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
- 第一行包含 N,包裹数量,以及 M,配送中心的数量,以空格分隔。
- 第二行包含 D_1, D_2, \ldots, D_N,每个包裹目的地的坐标,以空格分隔。
- 第三行包含 S_1, S_2, \ldots, S_M,每个配送中心的坐标,以空格分隔。
输出
在一行上打印最低总交货成本。
样本输入 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