排序后根据贪心可知连续的p个肯定是最优的,所以枚举遍历一遍即可,中间可以用前缀和做优化
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int T;
int a[N],sum[N];
int n,p;
int main(){
cin>>T;
for(int C=1;C<=T;C++){
cin>>n>>p;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
int ans=INF;
for(int i=p;i<=n;i++){
ans=min(ans,p*a[i]-(sum[i]-sum[i-p]));
}
printf("Case #%d: %d\n",C,ans);
}
return 0;
}