题目大意：将k对点两两相连，求最小长度
易证得，最优方案中，相连的办公楼一定是取相邻的比取不相邻的要更优
然后就可以用贪心来做这道题了。。
之前向CZL大神学习了用堆来贪心的做法orz
大概思路就是将初始所有的线段放进堆里
每次取最短的线段进行连接，且ans+=a[i]
取完后删除当前线段，与相邻的两条线段，同时再插入新边，权值为a[pre]+a[next]-a[now]
其作用与最大流中的反向弧有点像，下一次若取到这条边，即ans+=a[pre]+a[next]-a[now]
很明显a[now]与之前抵消了，即不取now，反而取相邻的两条边去了
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
*;
struct node{
int id;
};
priority_queue<node> Q;
int pre[maxn],next[maxn],k,a[maxn],n;
bool del[maxn];
int tot,last,now,ans;
bool operator<(node x, node y){
return a[x.id]>a[y.id];
}
int main(){
scanf("%d%d", &n, &k);
scanf("%d", &last);
tot=;
; i<n; i++){
scanf("%d", &now);
a[++tot]=now-last;
last=now;
}
; i<n; i++){
Q.push((node){i});
pre[i]=i-; next[i]=i+;
}
pre[]=next[tot]=;
a[]=; // Attention:不能是maxlongint，因为后面a[++tot]会爆
while (k--){
while (!Q.empty() && del[Q.top().id]) Q.pop();
if (Q.empty()) break;
int now=Q.top().id; ans+=a[now]; Q.pop();
int l=pre[now],r=next[now];
del[now]=del[l]=del[r]=;
a[++tot]=a[l]+a[r]-a[now]; Q.push((node){tot});
pre[tot]=pre[l]; next[tot]=next[r];
if (pre[tot]) next[pre[tot]]=tot;
if (next[tot]) pre[next[tot]]=tot;
}
printf("%d\n", ans);
;
}