【题目描述】
有 N 个人要参加国际象棋比赛,该比赛要进行 K 场对弈。
每个人最多参加两场对弈,最少参加零场对弈。
每个人都有一个与其他人不相同的等级(用一个正整数来表示)。
在对弈中,等级高的人必须用黑色的棋子,等级低的人必须用白色的棋子。
每人最多只能用一次黑色的棋子和一次白色的棋子。
为了增加比赛的可观度,观众希望 K 场对弈中双方的等级差的总和最小。
比如有 7 个选手,他们的等级分别是 30;17;26;41;19;38;18,要进行 3 场比
赛。最好的安排是 Player2 vs Player7,Player7 vs Player5,Player6 vs Player4 ,此时等级
差的总和等于(18-17)+(19-18)+(41-38)=5 达到最小。
【输入文件】
第一行两个正整数 N,K;
接下来有 N 行,第 i 行表示第 i+1 个人等级。
【输出文件】
在第一行输出最小的等级差的总和。
【样例输入】
7 3
30
17
26
41
19
38
18
【样例输出】
5
【数据规模】
在 90%的数据中,1<=N<=3000;
在 100%的数据中,1<=N<=100000;
保证所有输入数据中等级的值小于 10 8, 1<=k<=N-1.
按等级排序，一个点只会与相邻的两个点比赛
所以把差排序，取前k个的和
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long lol; 7 lol n,k,a[100001],s[100001],ans,num; 8 int main() 9 {int i; 10 cin>>n>>k; 11 for (i=1;i<=n;i++) 12 { 13 scanf("%lld",&a[i]); 14 } 15 sort(a+1,a+n+1); 16 for (i=1;i<=n;i++) 17 { 18 if (i>1) 19 { 20 num++; 21 s[num]=a[i]-a[i-1]; 22 } 23 } 24 sort(s+1,s+num+1); 25 for (i=1;i<=k;i++) 26 ans+=s[i]; 27 cout<<ans; 28 }