UVALive

题意：给出了你由n个数组成的序列，让你将这个序列分为成m个集合，使得每一个集合的最大值减最小值的差相加最小。（如果某集合只有一个数字，则最大值减最小值为0) 。

思路：首先我们不难想到，最优的分配方法一定是先给这n个数排序，然后将排序好的数分成m段。因为和一个数相差最小的数，就是在有序序列中与它相邻的数。

然后，要使得每段中最大值减最小值尽量小，那就应该尽量在相差较大的数字之间分段，这样就相当于抛弃了这一段差值。

比如，1，2，4，5，9，10。这六个数两两之间的差值分别为1，2，1，4，1.所以，如果要分成两段，应该在哪里分，当然是5和9之间，因为在所有的差值中，5和9是相差最多的，若在此处分段，表示你舍弃了大小为4的一段差值，而我们原本的目的就是舍弃尽量多的差值，使得最终的差值尽量小。如果要分成三段，那就是在2和4之间分，5和9之间分。

所以这题的解法就出来了：提前算出所有数之间的差值。然后在差值最大的几个数之间分段。

这题算最终结果还有个简便方法。就拿上面的例子来说。如果不分段，那最大值减最小值是9；如果分成两段，那就是在5和9之间分，两段的差值之和 = （5-1）+（10-9）=（10-1）-（9-5）=5。也就是说，最终结果会等于一开始的差值减去你舍去的差值。

具体看代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#define eps 1e-7
#define ll long long
#define inf 0x3f3f3f3f
#define pi 3.141592653589793238462643383279
using namespace std;

int cmp(int a,int b)
{
    return a>b;
}

int main()
{
    int t,n,m,cnt,a,b,res[105],num[105];
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; ++i)
            scanf("%d",&num[i]);
            
        sort(num,num+n); //先给所有的数排序 
        for(int i=1; i<n; ++i) //计算两两之间的差值 
            res[i-1] = num[i] - num[i-1];
            
        sort(res,res+n-1,cmp);//给差值按从大到小排序 
        int ans = num[n-1] - num[0]; //计算初始的最大差值 
        
        for(int i=0; i<m-1; ++i) //减去分段是舍弃的差值 
            ans -= res[i];
        printf("Case #%d: %d
",++cnt,ans);
    }
    return 0;
}