C++14(g++5.4) 解法, 执行用时: 199ms, 内存消耗: 9188K, 提交时间: 2020-06-06 22:55:37

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
typedef pair<ll,int>pii;
int n,k,l[N],r[N];
ll d[N];
void delete_d(int p)
{
	int left=l[p],right=r[p];
	l[right]=left;
	r[left]=right;
}
int main()
{
	scanf("%d%d",&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;
	set<pii>q;
	for(int i=0;i<=n;i++)
	{
		l[i]=i-1;
		r[i]=i+1;
		if(i>=1&&i<n)q.insert({d[i],i});
	}
	ll res=0;
	while(k--)
	{
		auto it=q.begin();
		ll a=it->first;
		int p=it->second,left=l[p],right=r[p];
		q.erase(it);
		q.erase({d[left],left});
		q.erase({d[right],right});
	    delete_d(left);
	    delete_d(right);
	    d[p]=d[left]+d[right]-d[p];
	    q.insert({d[p],p});
	    res+=a;
	}
	cout<<res<<endl;
    return 0;
}

C++ 解法, 执行用时: 96ms, 内存消耗: 6264K, 提交时间: 2021-09-13 09:53:23

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,a[N],pre[N],nxt[N],ans; 
struct node{
	int val,id;
	friend bool operator<(node x,node y){
		return x.val==y.val?x.id<y.id:x.val<y.val;
	} 
};
set<node>s;
void del(int x){
	nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x];
}
signed main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),pre[i]=i-1,nxt[i]=i+1;
	for(int i=1;i<n;i++) a[i]=a[i+1]-a[i],s.insert((node){a[i],i});
	a[0]=a[n]=1e9;
	for(int i=1;i<=k;i++){
		node x=*s.begin();
		int p=x.id,l=pre[p],r=nxt[p];
		ans+=x.val,del(l),del(r);
		s.erase((node){a[l],l}),s.erase((node){a[r],r}),s.erase(x);
		a[p]=a[l]+a[r]-a[p],s.insert((node){a[p],p});
	}
	printf("%d\n",ans);
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 56ms, 内存消耗: 4500K, 提交时间: 2023-07-28 20:39:26

#include<bits/stdc++.h>
using namespace std;
long long n,k,ans,a[1000001],pre[1000001],nxt[1000001],del[1000001];
struct cmp{
	inline long long operator()(long long x,long long y){return a[x]>a[y];}
};
priority_queue<long long,vector<long long>,cmp>q;
int main(){
	scanf("%lld%lld%lld",&n,&k,&a[1]);
	for(register int i=2;i<=n;++i)scanf("%lld",&a[i]),a[i-1]=a[i]-a[i-1];
	--n;a[0]=1e18;
	for(register int i=1;i<=n;++i)q.push(i),pre[i]=i-1,nxt[i]=i+1>n?0:i+1;
	while(k--){
		long long x=q.top();q.pop();
		while(del[x])x=q.top(),q.pop();
		ans+=a[x];del[pre[x]]=del[nxt[x]]=1,a[x]=a[pre[x]]+a[nxt[x]]-a[x];q.push(x);pre[x]=pre[pre[x]];nxt[x]=nxt[nxt[x]];nxt[pre[x]]=x;pre[nxt[x]]=x;
	}
	printf("%lld",ans);
}