游戏里面，队伍通过匹配实力相近的对手进行对战。但是如果匹配的队伍实力相差太大，对于双方游戏体验都不会太好。
给定n个队伍的实力值，对其进行两两实力匹配，两支队伍实例差距在允许的最大差距d内，则可以匹配。要求在匹配队伍最多的情况下匹配出的各组实力差距的总和最小。
输入描述
第一行两个整数，n，d。队伍个数n。允许的最大实力差距d。
2<=n <=50
0<=d<=100
第二行，n个整数，表示队伍的实力值，以空格分割。
0<=各队伍实力值<=100
输出描述
输出一个整数，表示各组对战的实力差值的总和。若没有队伍可以匹配，则输出-1。
示例1：输入输出示例仅供调试，后台判题数据一般不包含示例
输入
6 30
81 87 47 59 81 18
输出
57
示例2：输入输出示例仅供调试，后台判题数据一般不包含示例
输入
6 20
81 87 47 59 81 18
输出
12
示例3：输入输出示例仅供调试，后台判题数据一般不包含示例
输入
4 10
40 51 62 73
输出
-1
Java 代码
import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;
import java.math.BigInteger;
import java.util.stream.Stream;class Main {public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);// 处理输入int n = in.nextInt();int d = in.nextInt();int[] data = new int[n];for(int i = 0;i<n;i++){data[i] = in.nextInt();}// 按照大小排序Arrays.sort(data);//pair个数int[] dp1 = new int[n+1];//最小和int[] dp2 = new int[n+1];for (int i=2;i<n+1;i++){int tmp = 0;if (data[i-1] - data[i-2] <= d)tmp += 1;if (dp1[i-2]+tmp>dp1[i-1]){dp1[i] = dp1[i-2] + tmp;dp2[i] = dp2[i-2] + data[i-1] - data[i-2];}else if (dp1[i-2]+tmp<dp1[i-1]){dp1[i] = dp1[i-1];dp2[i] = dp2[i-1];}else{if (tmp == 1)dp2[i] = Math.min(dp2[i-1], dp2[i-2]+data[i-1]-data[i-2]);elsedp2[i] = Math.min(dp2[i-1], dp2[i-2]);dp1[i] = dp1[i-1];}}if (dp1[n] == 0)System.out.println(-1);elseSystem.out.println(dp2[n]);}}Python代码
import functools# 读取第一行的n
# 处理输入
params = [int(x) for x in input().split(" ")]
n = params[0]
target = params[1]
data = [int(x) for x in input().split(" ")]data.sort()dp1 = [0]*(n+1) #pair个数
dp2 = [0]*(n+1) #最小和for i in range(2,n+1):tmp = 0if data[i-1] - data[i-2] <= target:tmp += 1if dp1[i-2]+tmp>dp1[i-1]:dp1[i] = dp1[i-2] + tmpdp2[i] = dp2[i-2] + data[i-1] - data[i-2]elif dp1[i-2]+tmp<dp1[i-1]:dp1[i] = dp1[i-1]dp2[i] = dp2[i-1]else:if tmp == 1:dp2[i] = min(dp2[i-1], dp2[i-2]+data[i-1]-data[i-2])else:dp2[i] = min(dp2[i-1], dp2[i-2])dp1[i] = dp1[i-1]if dp1[n] == 0:print(-1)
else:print(dp2[n])JS代码
function main(n, target, data) {data.sort(function(a, b) {return a-b})let dp1 = new Array(n+1).fill(0)//pair个数let dp2 = new Array(n+1).fill(0) //最小和for (let i=2;i<n+1;i++){let tmp = 0if (data[i-1] - data[i-2] <= target)tmp += 1if (dp1[i-2]+tmp>dp1[i-1]) {dp1[i] = dp1[i-2] + tmpdp2[i] = dp2[i-2] + data[i-1] - data[i-2]}else if (dp1[i-2]+tmp<dp1[i-1]) {dp1[i] = dp1[i-1]dp2[i] = dp2[i-1]}else{if (tmp == 1)dp2[i] = Math.min(dp2[i-1], dp2[i-2]+data[i-1]-data[i-2])elsedp2[i] = Math.min(dp2[i-1], dp2[i-2])dp1[i] = dp1[i-1]}}if (dp1[n] == 0)console.log(-1)elseconsole.log(dp2[n])
}main(6, 30,[81, 87, 47, 59, 81, 18])
