自动搬运

查看原文

来自洛谷，原作者为

	LanFeng 长恨此身非我有，何时忘却营营？

搬运于2025-08-24 21:27:15，当前版本为作者最后更新于2017-11-19 16:53:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题题解有点少，还没有C++的（C应该也可以看懂），所以我来发布一篇

核心思路：现将各等级选手进行从小到大的排列，然后假设每人都会进行比赛，算出每相邻两人的差（这里不用再算不相邻的差了，因为要使和最小，离得最近的两数才满足。比如：1 2 3，2-1=1,3-1=2），再将差进行从小到大的排序 ，然后输出前K个数的和。

代码如下（头文件不用这么多，只用stdio和algorithm就可以了）：

#include<iostream> 
#include<cstdio> 
#include<cmath> 
#include<algorithm> 
#include<cstring>
using namespace std; 
int main()
{
    int n,k,i,a[100001],b[100001],ans=0;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    sort(a+1,a+n+1);//sort从小到大排序 
    for(i=1;i<=n-1;i++)
    b[i]=a[i+1]-a[i];//算出各等级选手的差 
    sort(b+1,b+n);//sort从小到大排序 
    for(i=1;i<=k;i++)
    ans+=b[i];//找出前K个等级差的和 
    printf("%d",ans);//输出 
    return 0;
}