用双向链表把相邻两项的差串起来,用大根堆维护价值,每次贪心取最大的$x$。取完之后打标记删掉$pre[x]$和$nxt[x]$,之后用$val[pre[x]]+val[nxt[x]]-val[x]$替换这个$x$塞进堆里去,注意边界要连上一个极值
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct a{long long val,pos;};
bool operator < (a x,a y)
{
return x.val>y.val;
}
priority_queue<a> hp;
int pre[N],nxt[N],del[N];
long long n,m,rd,last,ans,b[N];
void Delete(int pos)
{
del[pos]=true;
pre[nxt[pos]]=pre[pos];
nxt[pre[pos]]=nxt[pos];
}
int main ()
{
scanf("%lld%lld",&n,&m),n--,b[]=1e12;
pre[]=,nxt[]=,pre[n]=n-,nxt[n]=;
for(int i=;i<n;i++)
pre[i]=i-,nxt[i]=i+;
scanf("%lld",&last);
for(int i=;i<=n;i++)
{
scanf("%lld",&rd),b[i]=rd-last;
hp.push((a){b[i],i}),last=rd;
}
while(m--)
{
while(del[hp.top().pos]) hp.pop();
int p=hp.top().pos; hp.pop();
ans+=b[p],b[p]=b[pre[p]]+b[nxt[p]]-b[p];
hp.push((a){b[p],p}),Delete(pre[p]),Delete(nxt[p]);
}
printf("%lld",ans);
return ;
}