#J0023. [csp-j 2023模拟]百变机器人

[csp-j 2023模拟]百变机器人

题目描述:

魔法学院有 NN 个学生,其中第 ii 个学生的身高为 HiH_i 。保证 NN 是一个奇数。 同时,学院还有一个身高可调的百变机器人。那么,机器人和这些学生一共可以组成 N+12\frac {N+1}{2} 对。
已知百变机器人有 MM 种可调的身高 W1,W2,,WMW_1, W_2, … ,W_M,现在请你为机器人选择其中的一种身高,同时将机器人和学生进行任意配对,使得所有配对的身高差总和尽可能的小,求出该最小值。

输入格式:

第一行两个整数 N,MN, M; 第二行 NN 个整数,H1,H2,H3,,HNH_1, H_2, H_3, … , H_N
第三行 MM 个整数,W1,W2,W3,,WMW_1, W_2, W_3, … , W_M

输出格式:

一行一个整数,表示 N+12\frac {N+1}{2} 个配对的身高差总和的最小值。

样例:

5 3
1 2 3 4 7
1 3 8
3

提示

样例说明 机器人身高选择8,同时配对如下:(1,2), (3,4), (7,8)。 身高差总和为:|2-1|+{4-3|+|8-7|=3。

数据规模

  • 对于40%的数据,1N,M10001Hi,Wi1001≤N,M≤1000,1≤H_i,W_i≤100
  • 对于100%的数据,1N,M2×1051Hi,Wi1091≤N,M≤2×10^5,1≤H_i,W_i≤10^9