题目大意： 在n个点中，选出k对相邻的互不相同的点，使k段距离的总和最小。
贪心，双向链表。
首先，点之间的距离是动态的，所以要用堆来维护。
每次都选择最近的点。但因为其他情况，可能最终不会选择这对点连在一起
所以把俩个点旁边的路径的和减去俩个点之间距离再加进去，表示连旁边的俩条边，不连现在的边。
要维护许多信息。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 400000 + 10;
const int INF = 0x3f3f3f3f;
struct heap {
int v,i;
} h[maxn];
int p[maxn],pre[maxn],next[maxn],pos[maxn];
int n,m,ans=0,size=0; void pushup(int x) {
while(h[x].v<h[x>>1].v) {
pos[h[x>>1].i]=x;
swap(h[x],h[x>>1]);
x>>=1;
}
pos[h[x].i]=x;
} void push(int v,int i) {
h[++size].v=v;
h[size].i=i;
pos[i]=size;
pushup(size);
} void pushdown(int x) {
int to;
while(x <= size/2) {
to=x<<1;
if(to<size && h[to].v>h[to+1].v) to++;
if(h[x].v > h[to].v) {
pos[h[to].i]=x;
swap(h[x],h[to]);
x=to;
}
else break;
}
pos[h[x].i]=x;
} void del(int x) {
h[x].v = INF;
pushdown(x);
} void init() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=2;i<=n;i++) {
push(p[i]-p[i-1],i);
pre[i]=i-1; next[i]=i+1;
}
pre[2]=next[n]=0;
} void solve() {
int a,b;
heap k;
while(m--) {
k=h[1];
if(pre[k.i]==-1) {
ans+=k.v;
del(1); del(pos[next[k.i]]);
pre[next[next[k.i]]]=-1;
}
else if(next[k.i]==-1) {
ans+=k.v;
del(1); del(pos[pre[k.i]]);
next[pre[pre[k.i]]]=-1;
}
else {
ans+=k.v;
a=next[k.i]; b=pre[k.i];
pre[k.i]=pre[b]; next[pre[k.i]]=k.i;
next[k.i]=next[a]; pre[next[k.i]]=k.i;
h[1].v=h[pos[a]].v+h[pos[b]].v-h[1].v;
del(pos[a]); del(pos[b]);
pushdown(1);
}
}
printf("%d\n",ans);
} int main() {
init();
solve();
return 0;
}