问题 4782 --4. 足球联赛 (football)

4782: 4. 足球联赛 (football)

题目描述

  为了庆祝元旦, J 市决定举办全市小学足球联赛。各学校积极响应,共有 N支 球队报名参加,爱好足球的小 W也参加了。为了活动的开展和不影响学生学习,只 能安排 K 场比赛,每支球队最多参加两场比赛,至少参加零场比赛。因球队水平不 同,每支球队都拥有一个和其他球队不同的水平等级(用一个正整数来表示) 。在比 赛中,等级高的球队必须作为客场,等级低的球队必须作为主场。每个球队最多只 能做一次主场和一次客场。为了增加比赛的观赏度,观众希望 K 场比赛中球队水平 差距的总和最小。比如有 7 支球队,他们的等级分别是 30、17、26、41、19、38、 18,要进行 3 场比赛。那么最好安排是 球队 2  vs 球队 7, 球队 7 vs 球队 5 , 球队 6 vs 球队 4,此时等级差的总和等于 (18-17) + (19-18) + (41-38) = 5 达到最小。 

输入

第一行两个正整数 N ,K。 
接下来有 N 行,第 i 行表示第 i 支球队的等级。 

输出

共一行,输出最小的等级差的总和。 

样例输入输出

输入#1 复制
7 3
30
17
26
41
19
38
18
输出#1 复制
5

提示

【数据范围】 
对于 20%的数据, 1≤N≤300 
对于 80%的数据, 1≤N≤5000 
对于 100%的数据, 1≤N≤10000
保证所有输入数据中等级的值小于 32000,1 ≤K≤ N-1 

序号 标题 作者 发表时间 费用 操作