【华为OD-E卷 -47 最佳对手 100分（python、java、c++、js、c）】

25-03-07 19:21

2221

14080

blog.csdn.net

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷 - 最佳对手 100分（python、java、c++、js、c）】

题目

游戏里面，队伍通过匹配实力相近的对手进行对战。但是如果匹配的队伍实力相差太大，对于双方游戏体验都不会太好。
给定n个队伍的实力值，对其进行两两实力匹配，两支队伍实例差距在允许的最大差距d内，则可以匹配。
要求在匹配队伍最多的情况下匹配出的各组实力差距的总和最小

输入描述

第一行，n，d。队伍个数n。允许的最大实力差距d。

2<=n <=50 0<=d<=100 第二行，n个队伍的实力值空格分割。

0<=各队伍实力值<=100

输出描述

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

用例

用例一：

输入：

6 30
81 87 47 59 81 18
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2

输出：

57
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例二：

输入：

6 20
81 87 47 59 81 18
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2

输出：

12
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例三：

输入：

4 10
40 51 62 73
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2

输出：

-1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

python解法

解题思路：
该问题主要是对给定的一组数字进行分析，分段处理，计算每段中最小的差值总和，最后输出总的最小差值。如果某段内的数字的差值大于给定的阈值 d，则认为这一段结束，重新计算下一个段的差值。

解题步骤：
输入格式：

输入包含两个数字：n 和 d，n 表示数组 a 的长度，d 是差值的阈值。
然后是数组 a，表示一组整数。我们需要分析这组整数之间的差值。
主要逻辑：

计算数组 a 中相邻元素之间的差值。
如果两个相邻元素的差值大于 d，则认为这一段结束，计算这段的最小差值总和。
使用递归方法计算每段中最小的差值总和。
细节实现：

calc_min_diff：用于递归计算每段的最小差值总和。该函数通过递归计算可能的组合并记录最小的总和。
process_segment：用来遍历数组并处理每一段差值，按条件划分段落并调用 calc_min_diff 来计算最小差值总和。
solve：处理主逻辑，排序数组后调用 process_segment。
main：从标准输入获取数据并调用 solve 函数输出结果

import sys

# 计算最小的差值总和
def calc_min_diff(seg):
    # 初始化最小差值总和为一个非常大的数
    min_tot = [sys.maxsize]
    # 调用递归函数计算最小差值
    calc_pairs(seg, 0, False, 0, min_tot)
    return min_tot[0]

# 递归计算每一段的最小差值总和
def calc_pairs(seg, idx, skip, tot, min_tot):
    # 如果索引超出了范围，更新最小差值总和
    if idx >= len(seg):
        if tot < min_tot[0]:
            min_tot[0] = tot
        return

    # 计算包含当前元素的情况
    calc_pairs(seg, idx + 2, skip, tot + seg[idx], min_tot)

    # 如果没有跳过元素并且当前段长度为偶数，可以跳过当前元素，尝试另一种组合
    if not skip and len(seg) % 2 == 0:
        calc_pairs(seg, idx + 1, True, tot, min_tot)

# 处理每一段差值
def process_segment(a, d):
    res = 0  # 最终结果
    seg = []  # 存储当前段的差值
    match_found = False  # 标记是否找到有效的段

    # 遍历数组 a，计算相邻元素的差值
    for i in range(1, len(a)):
        dif = a[i] - a[i - 1]
        if dif > d:
            # 如果差值大于 d，认为这一段结束
            if seg:
                # 计算当前段的最小差值总和
                res += calc_min_diff(seg)
                seg.clear()  # 清空当前段
        else:
            # 如果差值小于等于 d，继续添加到当前段
            seg.append(dif)

    # 处理最后一个段
    if seg:
        res += calc_min_diff(seg)

    # 如果有有效的段，返回结果，否则返回 -1
    if res > 0:
        match_found = True

    return res if match_found else -1

# 主函数，处理输入并计算结果
def solve(n, d, a):
    a.sort()  # 对数组 a 排序
    return process_segment(a, d)  # 处理并返回结果

# 主程序入口，读取输入并输出结果
def main():
    n, d = map(int, input().split())  # 读取 n 和 d
    a = list(map(int, input().split()))  # 读取数组 a
    print(solve(n, d, a))  # 计算并输出结果

# 程序入口
if __name__ == "__main__":
    main()

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

java解法

解题思路
该问题的目标是通过比较数组中的相邻元素来计算差值，并将相邻差值小于给定阈值 lim 的一段数字组合在一起进行处理。每一段的差值组合需要通过递归的方式找到其最小差值总和。

具体的步骤包括：

排序数组：先对数组 power 进行排序，确保相邻元素的差值从小到大。
计算差值：计算相邻元素之间的差值（即每对元素之间的差）。
分段处理：根据差值是否超过阈值 lim 来判断是否结束当前段。如果差值大于 lim，则认为当前段结束，进行递归计算该段的最小差值。
递归计算：对于每一段中符合条件的差值，采用递归的方式计算它们的最小差值总和，递归中需要考虑跳过某些元素，以得到最小的差值。
最终返回结果：如果没有有效的段，返回 -1，否则返回所有段的最小差值总和。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int tms = in.nextInt();  // 读取输入的元素数量
        int lim = in.nextInt();  // 读取差值阈值
        int[] power = new int[tms];  // 用于存储元素的数组

        // 读取 power 数组的元素
        for (int i = 0; i < tms; i++) {
            power[i] = in.nextInt();
        }

        // 计算并输出最小差值总和
        System.out.println(minDiff(tms, lim, power));
    }

    // 计算最小差值总和的函数
    public static int minDiff(int tms, int lim, int[] power) {
        Arrays.sort(power);  // 对 power 数组进行排序
        int total = 0;  // 初始化最小差值总和
        boolean unmatched = true;  // 用于标记是否找到有效的匹配
        List<Integer> diffs = new ArrayList<>();  // 存储每段的差值

        // 遍历 power 数组并计算相邻元素之间的差值
        for (int i = 1; i < tms; i++) {
            int gap = power[i] - power[i - 1];  // 计算相邻元素之间的差值

            // 如果差值大于阈值 lim，则认为当前段结束
            if (gap > lim) {
                // 如果当前段有有效的差值，计算该段的最小差值
                if (!diffs.isEmpty()) {
                    unmatched = false;  // 找到有效的匹配
                    total += calcSum(diffs);  // 计算并累加当前段的最小差值总和
                    diffs.clear();  // 清空差值列表，准备下一段
                }
            } else {
                // 如果差值小于等于 lim，继续合并当前段
                diffs.add(gap);
            }
        }

        // 处理最后一段
        if (!diffs.isEmpty()) {
            unmatched = false;
            total += calcSum(diffs);  // 计算最后一段的最小差值
        }

        // 如果没有有效的段，返回 -1，否则返回总的最小差值总和
        return unmatched ? -1 : total;
    }

    // 计算一段差值的最小差值总和
    private static int calcSum(List<Integer> diffs) {
        int[] result = {Integer.MAX_VALUE};  // 用于存储最小差值总和，初始化为最大值
        match(diffs, 0, false, 0, result);  // 调用递归计算最小差值
        return result[0];  // 返回最小差值总和
    }

    // 递归匹配函数，计算最小差值总和
    private static void match(List<Integer> diffs, int idx, boolean skip, int sum, int[] result) {
        // 如果已经遍历完所有差值，更新最小差值总和
        if (idx >= diffs.size()) {
            result[0] = Math.min(result[0], sum);
            return;
        }

        // 包含当前差值的情况
        match(diffs, idx + 2, skip, sum + diffs.get(idx), result);

        // 如果没有跳过元素且当前段的长度为偶数，尝试跳过当前元素
        if (!skip && diffs.size() % 2 == 0) {
            match(diffs, idx + 1, true, sum, result);
        }
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

C++解法

解题思路

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

C解法

解题思路

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

JS解法

解题思路

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144918346"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

注册

评论记录：

未查询到任何数据！