【华为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
- 1
- 2
输出：
57
- 1
用例二：
输入：
6 20
81 87 47 59 81 18
- 1
- 2
输出：
12
- 1
用例三：
输入：
4 10
40 51 62 73
- 1
- 2
输出：
-1
- 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()
- 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);
}
}
}
- 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++解法
- 解题思路
更新中
- 1
C解法
更新中
- 1
JS解法
更新中
- 1
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：