Rt，$\operatorname{O(PVlog)}$的算法，结果比答案优是啥操作

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 3005
#define M 305
using namespace std;
int n,m,a[N],f[N][M],s[N];
int calc(int x,int y){
	int l=x,r=y,ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid]-a[x]<=a[y]-a[mid])ans=mid,l=mid+1;
		else r=mid-1;
	}
	return s[ans]-s[x-1]-a[x]*(ans-x+1)+a[y]*(y-ans)-(s[y]-s[ans]);
}
void solve(int l,int r,int ll,int rr,int op){
	if(l>r)return;
	int mid=(l+r)>>1;
	if(ll>=mid)return;
	int mn=ll;
	rep(i,ll,min(mid-1,rr))if(f[i][op-1]+calc(i,mid)<=f[mn][op-1]+calc(mn,mid))mn=i;
	f[mid][op]=f[mn][op-1]+calc(mn,mid);
	solve(l,mid-1,ll,mn,op);solve(mid+1,r,mn,rr,op);
}
int main(){
	//freopen("input","r",stdin);
	scanf("%d%d",&n,&m);
	rep(i,1,n)scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
	sort(a+1,a+n+1);
	memset(f,0x3f,sizeof(f));
	rep(i,1,n)f[i][1]=a[i]*i-s[i];//,cout<<f[i][1]<<" ";cout<<endl;
	//rep(i,1,n)rep(j,i+1,n)printf("%d %d %d\n",i,j,calc(i,j));
	rep(j,2,m){
		solve(j,n,j-1,n-1,j);
		//cout<<endl;
	}
	int ans=0x3f3f3f3f;
	rep(i,m,n)ans=min(ans,f[i][m]+a[n]*(n-i+1)-(s[n]-s[i-1]));//,cout<<i<<" "<<f[i][m]<<endl;//cout<<endl;
	printf("%d\n",ans);
	return 0;
}