题外话：

题解好像没有图，发个有图的，希望能帮助你们更好的理解

思路：

其实就是一个贪心吧，见的挺多的，一开始做的话很难想到这个反悔机制

转化问题

我们把每相邻两个办公楼之间的距离算出来，抽象出来点，也就是有n-1个点，第i个点的点权表示第i栋楼与第i+1栋楼的距离

那么，当我们选了第i个点时，我们就不能再选i-1,i+1这两个点了，为什么呢？因为选了第i个点的话，就不能再有电缆连接第i和第i+1栋楼了，而选i-1,i+1这两个点的话，又会连接一下第i或第i+1栋楼，不符合题意。

那么这样做了之后，题目就变为，给定n-1个点，要你选出k个点，并且这k个点两两不相邻（如果没看懂请重复看上面这段话）

那么问题转化了之后呢？？？

我们先来看一个错误的思路：

我们弄一个小根堆（本蒟蒻用的优先队列代替）

把每一个点放进去，然后每次贪心取最小值，取了一个点后就把相邻的点标记为不能取

如果你认为这是对的话，就看看下面这个样例（楼层5个，要连接电缆数2个）：

长方形是楼层，圆形是抽象出来的点，那么如果按照上面的思路的话，我们会先取1，也就是下图：

那么我们就只能取9了，答案就是10，可是，这是最优的吗？？

我们用肉眼都能看出来选择2,2更优,那么我们就要增添一个反悔机制：

当我们取了一个点后，我们要再加入一个点，这个点的权值为左边的点权+右边的点权-自身的点权,为什么这样就能反悔了呢？？

我们边模拟边解释：

当我们取了1点后，把两个2标记为访问过,并且更新1节点的左右，1节点左边已经空了，右边则是9节点，然后在1节点位置加入一个点权为2+2-1的点

如下图：

那么优先队列下一个点为2，而2被访问过了，直接下一个点，下一个点还是2，而2也被访问过了，再下一个点，下一个点为3，把与它相邻的9标记为访问过，而且现在已经取了2个点了（本样例题目规定了安装2条电缆）所以更新ans，并且退出

最后如下图：

看出来了吗？其实这就相当于我们取了2,2两个点，为什么呢？ans=1+3,也等于2+2呀，还记得3怎么来的吗？3=2+2-1，那么代回去就是

4=1+3=1+2+2-1=2+2

也就是说取了3这个点，就相当于没有取1这个点，而是取了2,2这两个点

你看懂了这个反悔机制吗qwq

至于左右节点的更新，我们用双向链表实现：

接下来是美滋滋的代码时间~~~

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define N 500007
#define inf 0x3f3f3f3f
using namespace std;
struct Place
{
    int val,l,r;
}p[N];
struct Node
{
    int val,id;
    bool operator <(Node it) const
    {
        return val>it.val;
    } 
};
int n,m,ans,last;
bool vis[N];
priority_queue<Node> q;
void Del(int x)
{
    p[x].l=p[p[x].l].l;
    p[x].r=p[p[x].r].r;
    p[p[x].l].r=x;
    p[p[x].r].l=x;
}
int main()
{
    scanf("%d%d%d",&n,&m,&last);
    for(int i=1;i<n;++i)
    {
        int in;
        scanf("%d",&in);
        p[i].val=in-last;
        last=in;
        p[i].l=i-1;
        p[i].r=i+1;
        q.push((Node){p[i].val,i});
    }
    p[0].val=p[n].val=inf;//注意这里 
    for(int i=1;i<=m;++i)
    {
        while(vis[q.top().id])
            q.pop();
        Node now=q.top();
        q.pop();
        ans+=now.val;
        vis[p[now.id].l]=vis[p[now.id].r]=1;
        p[now.id].val=p[p[now.id].l].val+p[p[now.id].r].val-p[now.id].val;
        q.push((Node){p[now.id].val,now.id});
        Del(now.id);
    }
    printf("%d",ans);
    return 0;
}