贪心+堆。
一般贪心题用到堆的时候都会存在一种反悔操作，因此这个题也不例外。
首先电缆一定是连接两个相邻的点的，这很好证明，其次一个点只能被一条电缆连接，所以我们通过选这个电缆，不选相邻电缆和选相邻电缆，不选这个电缆之间选择，然后添加反悔操作。
链表的存在是为了方便删除线段。用l,r分别表示该电缆链接之后左右两边第一个还可以反悔的电缆
#include <bits/stdc++.h>
#include <queue>
#define N 1001001
#define int long long
using namespace std;
int n, k;
struct da {
int dat, pos;
}data[1001001];
bool operator < (da a, da b) {
return a.dat > b.dat;
}
priority_queue <da> q; //小根堆
int l[N], r[N], a[N], d[N], vis[N], ans;
signed main()
{
scanf("%lld%lld", &n, &k);
int now, last;
scanf("%lld", &last);//把n个点里面的n-1条线段拆分成n-1个点。
for (int i = 1; i < n; i++)
{
scanf("%lld", &now);
data[i].pos = i;
data[i].dat = now - last;
last = now;
q.push(data[i]);
}
data[0].dat = data[n].dat = 2147483647;//因为要取最小值，所以初始赋为极大值。
for (int i = 1; i < n; i++)
l[i] = i - 1, r[i] = i + 1;//初始化链表
for (int i = 1; i <= k; i++)//取k个线段，其实就是取k个点
{
while (vis[q.top().pos])
{
q.pop();
}
da now = q.top();
q.pop();
ans += now.dat;
vis[l[now.pos]] = vis[r[now.pos]] = 1;
da nex;
nex.pos = now.pos;
nex.dat = data[now.pos].dat = data[l[now.pos]].dat + data[r[now.pos]].dat - data[now.pos].dat;//选这个点意味着还有一次反悔的操作.
l[now.pos] = l[l[now.pos]];
r[now.pos] = r[r[now.pos]];
r[l[now.pos]] = now.pos;
l[r[now.pos]] = now.pos;
q.push(nex);
}
printf("%lld", ans);
return 0;
}