匹配问题
时间限制: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