Luogu

分析

一个显然的想法是我们每次选能选的最短的一根。但是这样会有一些问题,就是选了最短的之后两边的就不能选了,然后答案会偏大。

这个其实比较好解决。假设当前最短的长度为 $l_u$,左右两边的长度分别为 $l_L$ 和 $l_R$,那么我们在选 $u$ 之后加一个长度为 $l_L+l_R-l_u$ 的候选项,表示删掉 $u$ 而选左右两个。这样子就是对的了。

用堆维护以上过程,双向链表维护左右的电缆即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;
typedef pair<int,int> pii;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,k,d[N];
int w[N],L[N],R[N],delv[N];
priority_queue<pii,vector<pii>,greater<pii> > Q;

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) d[i]=read();
    for (re int i=1;i<n;++i) {
        w[i]=d[i+1]-d[i],L[i]=i-1,R[i]=i+1;
        Q.push(make_pair(w[i],i));
    }
    L[1]=R[n-1]=0,w[0]=1e9; int ans=0,cnt=n-1;
    for (re int i=1;i<=k;++i) {
        while (!Q.empty()&&delv[Q.top().second]) Q.pop();
        if (Q.empty()) break;
        ans+=Q.top().first; int u=Q.top().second; Q.pop();
        delv[u]=delv[L[u]]=delv[R[u]]=1;
        w[++cnt]=w[L[u]]+w[R[u]]-w[u];
        L[cnt]=L[L[u]],R[L[cnt]]=cnt;
        R[cnt]=R[R[u]],L[R[cnt]]=cnt;
        Q.push(make_pair(w[cnt],cnt));
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 10 月 27 日 03 : 09 PM