不计算和存储前缀和,
利用代码中有注释的那部分来更新训练时间。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long ll;

int main(){
    int T, P, N;
    cin>>T;
    for(int i = 1; i <= T; i ++){
        cin>>N>>P;
        vector<ll> S(100000);
        for(int j = 0; j < N; j ++){
            cin>>S[j];
        }
        sort(S.begin(), S.begin() + N);
        ll sum, temp = 0;
        for(int j = 0; j < N - P + 1; j ++){
            if(j == 0){
                for(int k = j; k < j + P - 1; k ++){
                    temp += S[j + P - 1] - S[k];
                }
                sum = temp;
            }else{
                temp = temp + 
                (S[j + P - 1] - S[j + P -2])*(P - 1) - 
                (S[j + P - 2] - S[j - 1]);
                // 增加(P-1)个与上一个数的差值, 去掉上一个数与上一轮第一个数的差值
            }
            if(temp < sum) sum = temp;
        }
        cout<<"Case #"<<i<<": "<<sum<<endl;
    }
    return 0;
}