AT_abc181_e [ABC181E] Transformable Teacher

题目描述

有 $N$ 名学生，第 $i$ 名学生的身高为 $H_i$。$N$ 是奇数。

现在，包括你这位老师在内共有 $N+1$ 个人，需要将这 $N+1$ 个人分成 $\frac{N+1}{2}$ 对，每对由 2 人组成。

你的目标是使所有配对中身高差的总和最小。
也就是说，设第 $i$ 对的身高为 $(x_i, y_i)$，你希望最小化 $\displaystyle\sum_{i=1}^{(N+1)/2} |x_i - y_i|$。

你有 $M$ 种变身形态，第 $i$ 种变身形态的身高为 $W_i$。

请通过选择你的变身形态和合理地配对，使得所有配对中身高差的总和最小，并输出这个最小值。

输入格式

输入通过标准输入按以下格式给出。

$N$ $M$ $H_1$ $H_2$ $\dots$ $H_N$ $W_1$ $W_2$ $\dots$ $W_M$

输出格式

请输出通过选择变身形态和合理配对后，所有配对中身高差的总和的最小值。

输入输出样例 #1

输入 #1

5 3
1 2 3 4 7
1 3 8

输出 #1

3

输入输出样例 #2

输入 #2

7 7
31 60 84 23 16 13 32
96 80 73 76 87 57 29

输出 #2

34

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N, M \leq 2 \times 10^5$
• $N$ 是奇数。
• $1 \leq H_i \leq 10^9$
• $1 \leq W_i \leq 10^9$

样例解释 1

选择身高为 $8$ 的变身形态，并将身高配对为 $(1, 2),\ (3, 4),\ (7, 8)$，可以使总和最小。

由 ChatGPT 4.1 翻译