3743: 一般图最小匹配(第三轮01)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
给定n个点的完全图,第i个点上写有数字A 。由于是完全图，任意两个点之间都 有连边，点i和j之间的边的边权为∣ Ai − Aj ∣。
现在你希望求出这张图的最小m 匹配，最小m 匹配的定义如下：
从图中选出2 × m个点和m条边，每一条选中的边恰好连结两个选中的点，每一 个选中的点恰好被一条选中的边连结（即传统意义上的匹配）。 一种匹配的权值 定义为所有选中的边的边权和。
最小m 匹配要求找到一种匹配，使得其权值最小。
输出这个最小的权值。
输入
第一行两个正整数n, m代表总点数和要求的最小m 匹配。 接下来一行n个正整数Ai，代表每个点上写的数字。
输出
一行一个数字表示答案
样例输入 复制
4 1
2 4 7 3样例输出 复制
1提示
【数据范围】
对于20%的数据,1 ≤ n ≤ 10 对于40%的数据,1 ≤ n ≤ 100
对于另外10%的数据,1 ≤ m ≤ 50
对于另外20%的数据,1 ≤ Ai ≤ 5000
对于100%的数据， 1 ≤ 2 × m ≤ n ≤ 5000,1 ≤ Ai ≤ 10^9