首先进行排序，显然只有排序后相邻两个元素匹配才有可能成为答案。
我们设 \(b_i=a_i-a_{i-1}\)，则问题转化为：在 \(b\) 数组中选 \(m\) 个数（显然一个 \(b\)），两两不能相邻，求这些数和最小值。
就和这道题一模一样了，使用反悔贪心。
具体的，我们可以将所有 \(b_i\) 放进小根堆里，每次取出最小值，用链表维护这个点前面和后面没有被删或取出的点，记为 \(l\) 和 \(r\)。
然后我们可以将 \(b_l+b_r-b_x\) 推进堆里，然后删除 \(l\) 和 \(r\)。这是因为当 \(b_l+b_r\) 更优时，如果取了 \(b_x\) 后 \(b_l+b_r-b_x\) 为下一个最小值，那么答案累计的就是 \((b_l+b_r-b_x)+b_x\)，也就是 \(b_l+b_r\)，这样就保证了正确性。
code:
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define int long long
#define vi vector<int>
#define pb push_back
#define imp map<int,int>
#define debug printf("debug\n")
using namespace std;
const int N=100005;
int n,m,a[N],b[N],pre[N],nxt[N],ans=0,vis[N];
struct node{
int x,val;
friend bool operator < (node A,node B){
return A.val>B.val;
}
};
priority_queue<node>pq;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<n;i++){
b[i]=a[i+1]-a[i];
}
for(int i=1;i<n;i++){
// printf("%lld ",b[i]);
pre[i]=i-1;
nxt[i]=i+1;
pq.push((node){i,b[i]});
}
// printf("\n");
pre[1]=n-1;
nxt[n-1]=1;
// while(!pq.empty()){
// printf("%lld ",pq.top().val);
// pq.pop();
// }
while(m--){
while(vis[pq.top().x]) pq.pop();
node top=pq.top();
pq.pop();
ans+=top.val;
int x=top.x;
vis[pre[x]]=vis[nxt[x]]=1;
b[x]=b[pre[x]]+b[nxt[x]]-b[x];
pre[x]=pre[pre[x]];
nxt[x]=nxt[nxt[x]];
nxt[pre[x]]=x;
pre[nxt[x]]=x;
pq.push((node){x,b[x]});
}
printf("%lld\n",ans);
return 0;
}