← 返回题目列表

AtCoder · awc0035_b

B. 包裹配送中心

中文机器翻译题面 查看原题

分数: 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