洛谷P3620 [APIO/CTSC 2007]数据备份 学习笔记

#include <iostream>
#include <set>
#include<queue>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pll;
const int N = 100010;
int n, k;
int l[N], r[N];
LL d[N];
int vis[N];
void delete_node(int p){
    r[l[p]] = r[p];
    l[r[p]] = l[p];
}
priority_queue<pll,vector<pll>,greater<pll> > q;
int main(){
    cin >> n >> k;

    for (int i = 0; i < n; i ++ ) 
    cin >> d[i];
    for (int i = n - 1; i; i -- ) d[i] -= d[i - 1];

    d[0] = d[n] = 1e15;
    for (int i = 0; i <= n; i ++ ){
        l[i] = i - 1;
        r[i] = i + 1;
        q.push({d[i],i});
    }

    LL res = 0;
    while (k -- ){
        while(vis[q.top().second])
        q.pop();
        pll t=q.top();
        q.pop();
        int p = t.second, 
        left = l[p], right = r[p];
        vis[l[p]]=vis[r[p]]=1;
        delete_node(left), delete_node(right);
        res +=t.first;
        d[p] = d[left] + d[right] - d[p];
        q.push({d[p],p});
    }

    cout << res << endl;

    return 0;
}