题目大意：
为了使布线长度尽量小，每对布线的办公楼一定是相邻的，所以我们可以在读入时计算差分数组保存每相邻两个办公楼的距离，这样问题转化为，在差分数组 $b$ 中找 $k$ 个数，满足 $k$ 个数之和最小且互不相邻。
考虑一个最小的数 $x$，以及它旁边的两个数这样的组合：$(l,x,r)$
对于这 $3$ 个数，要么取 $x$，要么取 $l$ 和 $r$。不会只取 $l$ 或 $r$，因为不如取 $x$ 好：$x$ 既小，又不会对这 $3$ 个数之外的产生限制。
所以我们就有了下面这个很妙的贪心：
- 每次选最小的数 $x$，累计答案。
- 把 $3$ 个数缩起来：把 $x$ 及其两边的数删去，插入一个值为 $b[l]+b[r]−b[x]$ 的数。
进行 $k$ 次上述过程。
#include <cstdio>
#include <queue>
typedef long long LL;
const int N = 200005;
struct Pair {
LL x; int y;
bool operator < (const Pair &rhs) const {
return x > rhs.x;
}
};
std::priority_queue<Pair> Q;
int n, m, a[N], L[N], R[N]; LL b[N], ans; bool vis[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
--n;
for (int i = 1; i <= n; ++i) b[i] = a[i+1] - a[i];
for (int i = 1; i <= n; ++i)
L[i] = i - 1, R[i] = i + 1, Q.push((Pair){b[i], i});
b[0] = b[n+1] = b[n+2] = 1e18, L[0] = R[n+1] = n + 2;
for (int i = 1; i <= m; ++i) {
Pair now = Q.top();
while (vis[now.y]) Q.pop(), now = Q.top();
Q.pop(), ans += now.x;
int l = L[now.y], r = R[now.y];
vis[l] = vis[r] = true;
L[now.y] = L[l], R[now.y] = R[r], R[L[now.y]] = L[R[now.y]] = now.y;
b[now.y] = b[l] + b[r] - b[now.y];
Q.push((Pair){b[now.y], now.y});
}
printf("%lld\n", ans);
return 0;
}