华为OD机试 - 实力差距最小总和（Java 2024 E卷 200分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

游戏里面，队伍通过匹配实力相近的对手进行对战。

但是如果匹配的队伍实力相差太大，对于双方游戏体验都不会太好。

给定n个队伍的实力值，对其进行两两实力匹配，两支队伍实例差距在允许的最大差距d内，则可以匹配。

要求在匹配队伍最多的情况下，匹配出的各组实力差距的总和最小。

二、输入描述

第一行，n，d。队伍个数n。允许的最大实力差距d。(2<= n <=50, 0<= d <=100)。

第二行，n个队伍的实力值，空格分割。(0<=各队伍实力值<=100)。

三、输出描述

匹配后，各组对战的实力差值的总和。若没有队伍可以匹配，则输出-1。

四、解题思路

读取输入的队伍个数n和允许的最大实力差距d。
读取输入的队伍实力值数组scores，并对其进行排序。
初始化一个布尔变量flag为false，表示是否有两个队伍的实力差小于最大实力差距d。
初始化一个长度为n的整数数组arr，用于记录每个位置的实力差值总和。
- 将arr[0]设为0，表示只有一个队伍，无法匹配。
- 检查第一个队伍和第二个队伍的实力差值，如果小于等于最大实力差距d，则将arr[1]设为实力差值，同时将flag设为true。
- 对于后续的队伍i（i从2到n-1），检查队伍i和队伍i-1的实力差值，如果小于等于最大实力差距d，则将arr[i]设为arr[i-2]加上实力差值，表示在i和i-1之间的队伍可以匹配，同时将flag设为true。否则，将arr[i]设为arr[i-1]，表示无法匹配。
如果flag为true，表示存在可以匹配的队伍，输出arr[n-1]，即最后一个位置的实力差值总和。
否则，flag为false，表示无法匹配任意两支队伍，输出-1表示没有队伍可以匹配。

五、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();// 队伍个数nint n = nums[0];// 允许的最大实力差距dint d = nums[1];// n个队伍的实力值int[] scores = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();Arrays.sort(scores);// 是否有两个队伍的实力差小于最大实力差距d，如果没有返回-1boolean flag = false;// 前后队伍的实力差int[] arr = new int[n];arr[0] = 0;// 允许的最大实力差距dif (scores[1] - scores[0] <= d) {arr[1] = scores[1] - scores[0];flag = true;} else {arr[1] = 0;}for (int i = 2; i < n; i++) {if (scores[i] - scores[i - 1] <= d) {flag = true;arr[i] = arr[i - 2] + scores[i] - scores[i - 1];} elsearr[i] = arr[i - 1];}if (flag) {System.out.print(arr[n - 1]);} else {System.out.print(-1);}
}