2023年华为OD机考真题：最佳对手

全网最全面的华为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);
    }
}