全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：最佳对手
知识点排序DFS搜索回溯
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
游戏里面，队伍通过匹配实力相近的对手进行对战。
但是如果匹配的队伍实例相差太大，对于双方游戏体验都不会太好。
给定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。
示例2
输入：
6 20
81 87 47 59 81 18
输出：
12
说明：
最多能匹配成功4支队伍。
47与59配对，实力差距12；
81与81配对，实力差距0。
总实力差距12+0=12。
示例3
输入：
4 10
40 51 62 73
输出：
-1
说明：
实力差距都在10以上，没有队伍可以匹配成功。
解题思路：
先对数据进行排序，方便获取最短差距
分两步：
1、从前往后筛选一下符合实力差距的队伍，并求出最短差距和
2、从后往前筛选一下符合实力差距的队伍，并求出最短差距和
取上面两步的最小值
此算法只获得160分，有四个测试用例没过，分别4、12、15、20，4和12在下面，其他两个个没有
真机测试用例：
1 10 5 10 20 30 40 50 60 70 80 90 100 正确答案： -1
2 6 20 55 82 57 55 41 52 正确答案：5
4 8 10 65 44 45 58 40 60 46 47 正确答案：4
12 30 5 47 100 82 7 97 52 74 9 20 80 76 1 98 64 98 55 63 44 11 29 23 61 2 23 44 70 41 78 21 31 正确答案：27
代码实现：
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 最佳对手
* @Description 游戏里面，队伍通过匹配实力相近的对手进行对战。
* 但是如果匹配的队伍实例相差太大，对于双方游戏体验都不会太好。
* 给定n个队伍的实力值，对其进行两两实力匹配，两支队伍实例差距在允许的最大差距d内，则可以匹配。
* 要求在匹配队伍最多的情况下，匹配出的各组实力差距的总和最小。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int p = scanner.nextInt();
int[] in = new int[num];
for (int i = 0; i < num; i++) {
in[i] = scanner.nextInt();
}
in = Arrays.stream(in).sorted().toArray();
int result1 = 0;
for (int i = 0; i < in.length - 1; i++) {
if (!(in[i + 1] - in[i] > p)) {
result1 += (in[i + 1] - in[i]);
i++;
}
}
int result2 = 0;
for (int i = in.length - 1; i >= 1; i--) {
if (!(in[i] - in[i - 1] > p)) {
result2 += (in[i] - in[i - 1]);
i--;
}
}
int result = Math.min(result1, result2);
System.out.println(result == 0 ? -1 : result);
}
}
相关文章
