用双向链表把相邻两项的差串起来，用大根堆维护价值，每次贪心取最大的$x$。取完之后打标记删掉$pre[x]$和$nxt[x]$，之后用$val[pre[x]]+val[nxt[x]]-val[x]$替换这个$x$塞进堆里去，注意边界要连上一个极值
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100005; 7 struct a{long long val,pos;}; 8 bool operator < (a x,a y) 9 { 10 return x.val>y.val; 11 } 12 priority_queue<a> hp; 13 int pre[N],nxt[N],del[N]; 14 long long n,m,rd,last,ans,b[N]; 15 void Delete(int pos) 16 { 17 del[pos]=true; 18 pre[nxt[pos]]=pre[pos]; 19 nxt[pre[pos]]=nxt[pos]; 20 } 21 int main () 22 { 23 scanf("%lld%lld",&n,&m),n--,b[0]=1e12; 24 pre[1]=0,nxt[1]=2,pre[n]=n-1,nxt[n]=0; 25 for(int i=2;i<n;i++) 26 pre[i]=i-1,nxt[i]=i+1; 27 scanf("%lld",&last); 28 for(int i=1;i<=n;i++) 29 { 30 scanf("%lld",&rd),b[i]=rd-last; 31 hp.push((a){b[i],i}),last=rd; 32 } 33 while(m--) 34 { 35 while(del[hp.top().pos]) hp.pop(); 36 int p=hp.top().pos; hp.pop(); 37 ans+=b[p],b[p]=b[pre[p]]+b[nxt[p]]-b[p]; 38 hp.push((a){b[p],p}),Delete(pre[p]),Delete(nxt[p]); 39 } 40 printf("%lld",ans); 41 return 0; 42 }