2824 - Chess
有n个人要参加国际象棋比赛，该比赛要进行k场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人都不相同的等级（用一个正整数来表示）。在对弈中，等级高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为了增加比赛的客观度，观众希望k场对弈中上方的等级差的总和最小。比如有7个选手，他们的等级分别是30，17，26，41，19，38，18，要进行3场比赛。最好的安排是player 2 vs player 7, player 7 vs player 5, player 6 vs player 4,此时等级差的总和与（18-17）+（19-18）+（41-38）=5打到最小。
在90%的数据中，1≤n≤3000<br />
在100%的数据中，1≤n≤100000
保证所有输入数据中等级的值小于108，1≤k≤n-1
Input
第一行两个正整数n，k。
接下来有n行，第i行表示第i-1和人等级。
Output
在第一行输出最小的等级差的总和。
Examples
Input
7 3 30 17 26 41 19 38 18
Output
5
Solution C++
#include<cstdio> #include<algorithm> using namespace std; int n,m; int a[110000]={0}; int cha[110000]={0}; long long ans=0; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<n;i++) cha[i]=a[i+1]-a[i]; sort(cha+1,cha+n); for(int i=1;i<=m;i++) ans+=cha[i]; printf("%d",ans); }