分数: 500 点
问题陈述
有 N 幼儿园里的孩子们。的高度 i第一个孩子是 H_i。在这里, N 是奇数。
你、老师和这些孩子 - N+1 人总数 - 将使 \large\frac{N+1}2 对。
您的目标是最小化这些对的身高差异之和。 也就是说,你想最小化 \displaystyle \sum_{i=1}^{(N+1)/2}|x_i-y_i|,其中 (x_i, y_i) 是人的身高对 i第对。 您可以转换成的
你有 M 形式。你的身高在 i-th 形式是 W_i.
找到所有对的高度差异的最小可能总和,通过最佳选择你的形式和配对来实现。
约束
- 输入中的所有值都是整数。
- 1 \leq N, M \leq 2 \times 10^5
- N 是奇数。
- 1 \leq H_i \leq 10^9
- 1 \leq W_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N M H_1 \dots H_N W_1 \dots W_M
输出
打印所有对的高度差的最小可能总和,这是通过最佳选择形式和配对来实现的。
示例输入 1
5 3 1 2 3 4 7 1 3 8
示例输出 1
3
通过选择具有高度的形式来最小化最小值 8 并与高度配对 (1, 2), (3, 4),和 (7, 8).
示例输入 2
7 7 31 60 84 23 16 13 32 96 80 73 76 87 57 29
示例输出 2
34
示例输入 3
15 10 554 525 541 814 661 279 668 360 382 175 833 783 688 793 736 496 732 455 306 189 207 976 73 567 759
示例输出 3
239