最佳对手实力差距最小总和

题目描述

游戏里面，队伍通过匹配实力相近的对手进行对战。但是如果匹配的队伍实力相差太大，对于双方游戏体验都不会太好。

给定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

说明

18与47配对，实力差距29

59与81配对，实力差距22

81与87配对，实力差距6

总实力差距29+22+6=57

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

//最佳对手实力差距最小总和

/**
  动态规划五部曲：
 1.dp[i]数组含义：代表 i 个队伍能匹配的队伍数量
 2.递推公式：if (dp[i - 1] < dp[i - 2] + 1) {dp[i] = dp[i - 2] + 1;  }
  表示如果当前队伍i能和i-1配对， 并且 配对后的总对数dp[i-2]+1 比不配对i的总对数dp[i - 1]更多，则匹配i ；反之不匹配队伍i，dp[i]=dp[i-1]
 3.初始化dp数组： 队伍小于等于2的情况
 4.遍历顺序，从左往右
 5.打印dp数组
 */

public class Solution200_20 {
    // 通用 split 函数
    public static List<String> split(String str, String delimiter) {
        return Arrays.asList(str.split(delimiter));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), d = scanner.nextInt();
        scanner.nextLine(); // 处理换行符

        String s = scanner.nextLine();
        List<String> ansStr = split(s, " ");
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            ans[i] = Integer.parseInt(ansStr.get(i));
        }

        // 排序
        Arrays.sort(ans);

        // 1.dp数组含义：dp[i] 代表 i 个队伍能匹配的队伍数量
        int[] dp = new int[n];

        // minSum[i] i 个队伍匹配之后差值的和
        int[] minSum = new int[n];

        //2.初始化dp数组, 当只有两只队伍，并且能够组成1队，则dp[1]=1。
        if (ans[1]-ans[0]<=d){
            dp[1]=1;
            minSum[1]=ans[1]-ans[0];
        }

        for (int i = 2; i <n; i++) {
            //如果当前队伍和上一个队伍能够匹配
            boolean canMatch = ans[i] - ans[i - 1] <= d;

            if (canMatch) {
                // 优先选择匹配数量多的，匹配数量相等的选择差异值和小的

                //dp[i-1] 表示 i-1个队伍最大匹配对数 ；dp[i-2]表示 i-2队伍最大匹配对数 ， +1表示 当前 队伍i要和i-1组成一队
                //如果和当前i队伍匹配能获得更多队伍数量，则队伍i加入
                if (dp[i - 1] < dp[i - 2] + 1) {
                    dp[i] = dp[i - 2] + 1;
                    minSum[i] = minSum[i - 2] + ans[i] - ans[i - 1];
                }
                //如果当前队伍i和i-1配对后的总对数 不变，则取总实力差值最小的情况：
                // 1. i和i-1配对:minSum[i - 2] + ans[i] - ans[i - 1]；
                // 2.i不进行配对（直接取i-1的总实力差值）
                //注意：i和i-1配对后，只会出现 配对对数变多或者不变 ，不可能出现变少的情况！！
                else {
                    dp[i] = dp[i - 1];
                    minSum[i] = Math.min(minSum[i - 1], minSum[i - 2] + ans[i] - ans[i - 1]);
                }
            //如果当前队伍实力无法匹配上一个队伍，则直接复制i-1的值
            } else {
                dp[i] = dp[i - 1];
                minSum[i] = minSum[i - 1];
            }
        }

        System.out.println(dp[n-1] == 0 ? -1 : minSum[n-1]);
    }
}