跟着第一篇题解的思路写的，但是只有25pts

玄1关

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], n, k, l[N], r[N];
bool vis[N];  // 因为队列中可能会有现在不需要/访问过的节点，所以我们在取堆顶元素的时候加一个判定
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii>> q;
int main() {
    cin >> n >> k;
    int prefix = 0;
    cin >> prefix;
    // 为了减轻查找负担，我们使用双向链表记录节点左右没有被访问过的最近的公司的下标
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        p[i] = x - prefix;  // p[i-1]并不是原生数据，是差分后的距离，所以不能直接减
        prefix = x;
        // cout << p[i] << " ";
        l[i] = i - 1;
        r[i] = i + 1;
        q.push({p[i], i});
    }
    int ans = 0;
    p[0] = p[n] = INT_MAX;  // 设为极大值
    for (int i = 1; i <= k; i++) {
        pii x = {-1, -1};
        while (vis[q.top().second]) {
           
            q.pop();
        } 
		x = q.top();
        ans += x.first;  // 贪心选择当前最优节点
        vis[l[x.second]] = 1;
        vis[r[x.second]] = 1;
        p[x.second] = p[l[x.second]] + p[r[x.second]] - p[x.second];
        l[x.second] = l[l[x.second]];  // 需要修改相邻节点的相邻节点还有当前节点的链表指针，如果有一个没有修改就会导致链表断裂
        r[x.second] = r[r[x.second]];
        r[l[x.second]] = x.second;
        l[r[x.second]] = x.second;
        q.push({p[x.second], x.second});  // 重新入队供后续反悔
    }
    cout << ans << endl;
}