问题 4435 --2、最佳观赏度 (best)

4435: 2、最佳观赏度 (best)

题目描述

   学校准备举办一场乒乓球赛,有N位选手报名参加,报名时需登记自己的水平等级P。比赛共有K场,每位选手最多参加两场比赛,最少参加零场比赛。 
每位选手不能两场都找等级比他低的,或都比他高的。
为了增加比赛的观赏性,定义观赏度S为:K场比赛中,双方等级差的总和。S越小,观赏度越高。求这K场比赛的最佳观赏度,即观赏度S的最小值。 
比如有7个选手,他们的等级分别为:30、17、26、41、19、38、18,要进行3  场比赛,则观赏度S的最小值为:(18-17)+(19-18)+(41-38)=5。

输入

第1行两个正整数N,K。 接下来共N行,第i行表示第i-1位选手的水平等级。

输出

共1行,输出达观赏度S的最小值。

样例输入输出

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

提示

90%的数据:1<=N<=3000; 
100%的数据:1<=N<=100000. 
保证所有数据均在1~10^9范围内,1<K<N。

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