象棋比赛

Y-E-T-I 2021-10-27 原文

【题目描述】
有 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 }