/ Vijos / 题库 /

匹配问题

匹配问题

时间限制:1秒  内存限制:256M


【问题描述】

  两个整数集合 \(S_1、S_2\),集合 \(S_1\) 的元素个数为 \(N\),集合 \(S_2\) 的元素个数为 \(M\),且 \(N<=M\)。现在需要从 \(S_2\) 中选出 \(N\) 个元素,使得两个集合的匹配差最小。对于两个集合的匹配差在本题定义作此描述:
  定义 \(F(S1,S2)=min\{|a_1-b_1| + |a_2-b_2| + ... + |a_n-b_n|\}\)( \(n\) 为 \(S_1\) 的元素个数,\(ai∈S_1,b_i∈S2\)),\(F(S1,S2)\) 即为 \(S_1\) 和 \(S_2\) 的匹配差。
  例如:\(S_1=\{2,4\}、S_2=\{6,5,2\}\),则从\(S_2\) 中选择两个元素的集合有:\(\{6,5\}、\{6,2\}、\{5,2\}\),他们的匹配差分别为:
  \(F_1(S_1,S_2)=min\{|2-6|+|4-5|, |2-5|+|4-6|\}=5\)
  \(F_2(S_1,S_2)=min\{|2-6|+|4-2|, |2-2|+|4-6|\}=2\)
  \(F_3(S_1,S_2)=min\{|2-5|+|4-2|, |2-2|+|4-5|\}=1\)
  所以最小匹配差为 \(1\)。

【输入格式】

  第一行两个数:\(N,M\),其中 \(N\) 表示第一堆零件的个数,\(M\) 表示第二堆元素的个数。
  接下来 \(N\) 行,每行一个数,表示 \(S_1\) 的各个元素(不超过\(10000\))。
  再接下来 \(M\) 行,每行一个数,表示 \(S_2\) 的各个元素(同样不超过\(10000\))。

【输出格式】

  表示两个集合的匹配差值的最小值。

【输入输出样例】

 Input

4 5
1
2
3
4
5
6
7
8
9

 Output

16

【数据限制】

  \(0 < N <= M <= 1000\)
  集合中的每个元素不超过 \(10000\)。
  

【来源】

  Mr.he

信息

ID
1170
难度
4
分类
动态规划 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者