算法竞赛进阶指南，85 页，堆排序
本题要点：
1、d[i] 表示公司 i 和 i - 1 之间的距离，选择k段距离，使得总和最小。
显然，相邻的两个距离不能选择；假设
1）所有的距离最小的是 d[i];
2）除了 d[i - 1], d[i], 和 d[i + 1] 这三个，剩下的 成为 剩余距离;
3）剩余距离中，最小的距离是 d[j] // j != i - 1, i, i + 1
2、本题的结论：要么选择 d[i] + d[j], 要么选择 d[i - 1] + d[i + 1]
假如选择了d[i - 1], 然后在 剩余距离中选择一个（显然，只能选择d[j], 因为d[j] 是剩余距离中最小的），
d[i - 1] + d[j] < d[i] + d[j] //因为 d[i] 是所有距离中最小的；
因此结论成立；
3、 用双向链把所有的距离 d[i] 连起来，每次选出最小的 d[i]（ans 累加）, 然后删除 d[i - 1], d[i], d[i + 1],
再把 d[i - 1] + d[i + 1] - d[i] 插入到刚刚删除的地方;
如果下次选出来的最小元素 是 d[i - 1] + d[i + 1] - d[i]， 相当于选择了 d[i - 1] + d[i + 1]， 否则相当于选择了
d[i] + d[j] （剩余距离中，最小的距离是 d[j]）
4、 这里使用了集合 set 来存储， （d[mid], mid）某段的距离 和 下标， 数组 L[MaxN], R[MaxN]，存放的是某段的前后相邻的段的下标；
然后每次选出 最小的距离 d[mid], 删除 自身和左右相邻的 段， 再插入 （d[left] + d[right] - d[mid], mid）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;
typedef long long LL;
const int MaxN = 100010;
typedef pair<LL, int> PLI;
int n, k;
int L[MaxN], R[MaxN]; //链表的前后节点
LL d[MaxN]; //相邻两点的距离void del_node(int p) //删除第p个节点
{
L[R[p]] = L[p];R[L[p]] = R[p];
}int main()
{
scanf("%d%d", &n, &k);for(int i = 0; i < n; ++i){
scanf("%lld", &d[i]);}for(int i = n - 1; i > 0 ; --i){
d[i] = d[i] - d[i - 1]; //这里的 d[i] 表示节点 i - 1 和i之间的距离}d[0] = d[n] = 1e15;set<PLI> s;for(int i = 0; i <= n; ++i){
L[i] = i - 1;R[i] = i + 1;s.insert(make_pair(d[i], i));}set<PLI>::iterator it = s.begin();LL ans = 0;int left, mid, right;while(k--){
it = s.begin();ans += it->first;mid = it->second;left = L[mid], right = R[mid];
// printf("left = %d, mid = %d, right = %d\n", left, mid, right);d[mid] = d[left] + d[right] - d[mid];s.erase(it);if(left > 0 && left < n){
s.erase(s.find(make_pair(d[left], left)));del_node(left);}if(right > 0 && right < n){
s.erase(s.find(make_pair(d[right], right)));del_node(right);}s.insert(make_pair(d[mid], mid));}printf("%lld\n", ans);return 0;
}/* 5 2 1 3 4 6 12 *//* 4 */