最佳对手实力差距最小总和
题目描述
游戏里面,队伍通过匹配实力相近的对手进行对战。但是如果匹配的队伍实力相差太大,对于双方游戏体验都不会太好。
给定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]); } }