Java(javac 1.8) 解法, 执行用时: 1125ms, 内存消耗: 87856K, 提交时间: 2019-12-07 15:39:09

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t--!=0)
		{
			int n=sc.nextInt();
			int k=sc.nextInt();
			int[] a=new int[n];
			for(int i=0;i<n;i++)
				a[i]=sc.nextInt();
			Arrays.sort(a);
			if(k==1)
				System.out.println(0);
			else
			{
				if(n%2==0)
				{
					int sum=0;
					for(int i=0;i<n;i+=2)
					{
						sum+=a[i+1]-a[i];
					}
					System.out.println(sum);
				}
				else
				{
					int min=0x3f3f3f3f;
					for(int i=0;i<n-2;i+=2)
					{
						int sum=0;
						for(int j=0;j<n;j+=2)
						{
							if(i==j)
							{
								sum+=a[j+2]-a[j];
								j++;
							}
							else
								sum+=a[j+1]-a[j];
						}
						min=Math.min(sum, min);
					}
					System.out.println(min);
				}
			}
		}
		sc.close();
	}

}

C++11(clang++ 3.9) 解法, 执行用时: 20ms, 内存消耗: 484K, 提交时间: 2019-12-13 19:53:12

#include <stdio.h>
#include <algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
long long d[100005],a[100005];
int main()
{
 	int t,n,k;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		sort(a+1,a+1+n);
		for(int i=1;i<=k-1;i++)d[i]=INF;
		for(int i=1;i<=n;i++)
		{
			if(i%k)
			{
				if(i>k)
					d[i]=min(d[i-k]+a[i]-a[i-k+1],d[i-1]+a[i]-a[i-1]);
			}
			else d[i]=d[i-k]+a[i]-a[i-k+1];
		}
		printf("%lld\n",d[n]);
	}
}