#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define INF 0x3fffffff
#define pa pair<int,int>
int n,k,pre[maxn],nxt[maxn],len[maxn];
priority_queue<pa,vector<pa>,greater<pa> >
q;
int main(){
scanf("%d%d",&n,&
k);
int now,last=
0;
for(
int i=
1;i<=n;i++
){
scanf("%d",&
now);
len[i]=now-
last;
last=
now;
pre[i]=i-
1;nxt[i]=i+
1;
}//len[1]是没用的
pre[
2]=
0,nxt[n]=
0;
for(
int i=
2;i<=n;i++
)
q.push(make_pair(len[i],i));
int ans=
0;
while(k--
){
while(q.top().first!=
len[q.top().second])
q.pop();//这一步不能省略
pa tmp=
q.top();q.pop();
int pos=
tmp.second;
int l=pre[pos],r=
nxt[pos];
ans+=
tmp.first;
pre[nxt[pos]=nxt[r]]=
pos;
nxt[pre[pos]=pre[l]]=
pos;
len[pos]=l&&r?min(INF,len[l]+len[r]-
len[pos]):INF;
len[l]=len[r]=
INF;
q.push(make_pair(len[pos],pos));
}
printf("%d\n",ans);
}
转载于:https://www.cnblogs.com/zsben991126/p/10247587.html
