题目描述

作为一名学校足球教练，你的任务是挑选一支由P个学生组成的团队代表你的学校。

共有N名学生供你挑选，第 i 名学生的技术等级为Si，这是一个正整数，表示他们的技术水平。

在你看来一个合理的团队中的P个球员的技术应该是相当的，这样才能使每个人都融入到队内。

在最开始，你可能无法直接选出一个配置合理的队伍，因此你将为一些学生提供一对一的辅导。

将一名学生的技术等级提高1需要你花费1个小时的时间来进行辅导。

比赛季很快就开始了（事实上，第一场比赛已经开始了！），所以你想知道训练出一个合理的团队，你需要提供的最少训练小时数是多少。

输入格式
第一行包含整数T，表示共有T组测试数据。

每组测试数据的第一行包含两个整数N和P。

第二行包含N个整数SiSi，其中第 i 个整数为第 i 个学生的技术等级。

输出格式
每组数据输出一个结果，每个结果占一行。

结果表示为“Case #x: y”，其中x为组别编号（从1开始），y为所需的最少训练小时数。

数据范围

$1≤T≤1001≤T≤100$,

$1≤Si≤100001≤Si≤10000$,

$2≤P≤N2≤P≤N$,

$2≤N≤1052≤N≤105$

样例

输入样例：

3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7

输出样例：

Case #1: 14
Case #2: 0
Case #3: 6

样例解释
在样例＃1中，你可以花费总共6个小时训练第一个学生，8个小时训练第二个学生，使得前三个学生的技能水平同为9。这是你可以花费的最短时间，因此答案是14。

在样例＃2中，你可以选择直接选择前两个学生而无需进行任何指导，因此答案为0。

在样例＃3中，P = N，因此每个学生都将加入您的团队。 你必须花6个小时训练第三个学生，这样所有人的技术等级都为7。 这是你可以花费的最短时间，所以答案是6。

算法

时间复杂度为:$O(nlogn)$
空间复杂度为:$O(1)$

时间复杂度分析：排序+遍历, 为$O(nlogn)$
空间复杂度分析：由于没有存储前缀和, 所以额外空间为$O(1)$

C++ 代码

#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;
}