思路：dp[i]=dp[j]+sum[i]-sum[j]-(i-j)*num[j+1];
然后就是比较斜率。
注意的时这里j+t<=i；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Maxn 400010
#define LL __int64
using namespace std;
LL num[Maxn],sum[Maxn],dp[Maxn];
int que[Maxn*];
LL Getleft(int j,int k)
{
return dp[j]-sum[j]+j*num[j+]-(dp[k]-sum[k]+k*num[k+]);
}
LL Getright(int j,int k)
{
return num[j+]-num[k+];
}
int main()
{
int n,t,head,rear;
LL i,j;
while(scanf("%d%d",&n,&t)!=EOF){
memset(dp,,sizeof(dp));
for(i=;i<=n;i++){
scanf("%I64d",num+i);
}
sort(num+,num+n+);
for(i=;i<=n;i++){
sum[i]=num[i]+sum[i-];
}
head=,rear=;
que[++rear]=;
for(i=t;i<=n;i++){
j=i-t+;
while(head<rear&&Getleft(que[head+],que[head])<=Getright(que[head+],que[head])*i){
head++;
}
dp[i]=dp[que[head]]+sum[i]-sum[que[head]]-(i-que[head])*num[que[head]+];
while(head<rear&&j>=t&&Getleft(j,que[rear])*Getright(que[rear],que[rear-])<=Getleft(que[rear],que[rear-])*Getright(j,que[rear])){
rear--;
}
if(j>=t)
que[++rear]=j;
}
printf("%I64d\n",dp[n]);
}
return ;
}