题目描述与示例
题目描述
某个产品当前迭代周期内有 N 个特性（F1, F2, ..., FN）需要进行覆盖测试，每个特性都被评估了对应的优先级，特性使用其 ID 作为下标进行标识。
设计了 M 个测试用例（T1, T2, ..., TN ），每个用例对应了一个覆盖特性的集合，测试用例使用其 ID 作为下标进行标识，测试用例的优先级定义为其覆盖的特性的优先级之和。
在开展测试之前，需要制定测试用例的执行顺序，规则为：优先级大的用例先执行，如果存在优先级相同的用例，用例 ID 小的先执行。
输入描述
第一行输入为 N 和 M ，N 表示特性的数量，M 表示测试用例的数量，0＜N<=100 ，0＜M<=100 之后 N 行表示特性 ID=1 到特性 ID=N 的优先级。 再接下来 M 行表示测试用例 ID=1 到测试用例 ID=M 关联的特性的 ID 的列表。
输出描述
按照执行顺序（优先级从大到小）输出测试用例的 ID，每行一个 ID。 测试用例覆盖的 ID 不重复。
示例一
输入
5 4
1
1
2
3
5
1 2 3
1 4
3 4 5
2 3 4
输出
3
4
1
2
说明
测试用例的优先级计算如下：
T1=Pf1+Pf2+Pf3=1+1+2=4
T2=Pf1+Pf4=1+3=4
T3=Pf3+Pf4+Pf5=2+3+5=10
T4=Pf2+Pf3+Pf4=1+2+3=6
按照优先级从小到大，以及相同优先级，ID 小的先执行的规则，执行顺序为 T3,T4,T1,T2
示例二
输入
3 3
3
1
5
1 2 3
1 2 3
1 2 3
输出
1
2
3
说明
测试用例的优先级计算如下：
T1=Pf1+Pf2+Pf3=3+1+5=9
T2=Pf1+Pf2+Pf3=3+1+5=9
T3=Pf1+Pf2+Pf3=3+1+5=9
每个优先级一样，按照 ID 从小到大执行，执行顺序为 T1,T2,T3
解题思路
又是一道典型的直接看用例比看题意更容易理解的题目。
对于每一个测试用例 ID都对应一个优先级，而这个优先级的计算是若干特性的优先级的叠加。
假设所有特性对应的优先级已经储存在哈希表dic中，dic[num]表示特性num的优先级。
对于特定的测试用例，包含了若干特性的测试num1, num2, ...，这个测试用例的总优先级为dic[num1] + dic[num2] + ...
最终再进行排序和逐行输出即可。
代码
Python
# 题目：【哈希表】2023C-测试用例执行计划
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：哈希表/排序
# 代码看不懂的地方，请直接在群上提问
# 输入特性个数N，测试用例个数M
N, M = map(int, input().split())
# 构建一个哈希表，用于储存每一个特性的优先级
dic = dict()
# 输入N行，key为编号i，value为该特性的优先级
for i in range(1, N+1):
dic[i] = int(input())
# 构建答案哈希表
ans_dic = dict()
# 输入M行
for i in range(1, M+1):
# 获得第i个测试用例对应的特性
nums = list(map(int, input().split()))
# 将所有特性的优先级进行求和，得到用例i的特性
ans_dic[i] = sum(dic[num] for num in nums)
# 对所有的id根据优先级大小进行排序，先按照优先级降序排序，优先级相同再按照id大小升序排序
# 然后逐行输出
for idx in sorted(list(ans_dic.keys()), key = lambda x: (-ans_dic[x], x)):
print(idx)
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入特性个数N，测试用例个数M
int N = scanner.nextInt();
int M = scanner.nextInt();
scanner.nextLine(); // Consume newline character
// 构建一个哈希表，用于储存每一个特性的优先级
Map<Integer, Integer> dic = new HashMap<>();
// 输入N行，key为编号i，value为该特性的优先级
for (int i = 1; i <= N; i++) {
int priority = scanner.nextInt();
dic.put(i, priority);
}
scanner.nextLine(); // Consume newline character
// 构建答案哈希表
Map<Integer, Integer> ansDic = new HashMap<>();
// 输入M行
for (int i = 1; i <= M; i++) {
String line = scanner.nextLine();
Scanner lineScanner = new Scanner(line);
// 获得第i个测试用例对应的特性
List<Integer> nums = new ArrayList<>();
while (lineScanner.hasNextInt()) {
int num = lineScanner.nextInt();
nums.add(num);
}
// 将所有特性的优先级进行求和，得到用例i的特性
int sum = 0;
for (int num : nums) {
sum += dic.get(num);
}
ansDic.put(i, sum);
lineScanner.close();
}
// 对所有的id根据优先级大小进行排序，先按照优先级降序排序，优先级相同再按照id大小升序排序
List<Integer> ids = new ArrayList<>(ansDic.keySet());
Collections.sort(ids, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
int diff = ansDic.get(b) - ansDic.get(a);
return diff != 0 ? Integer.compare(diff, 0) : Integer.compare(a, b);
}
});
// 然后逐行输出
for (int idx : ids) {
System.out.println(idx);
}
scanner.close();
}
}
C++
“`C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <sstream>
using namespace std;
int main() {
// 输入特性个数N，测试用例个数M
int N, M;
cin >> N >> M;
cin.ignore(); // Ignore the newline character after M
<pre><code>// 构建一个哈希表，用于储存每一个特性的优先级
unordered_map<int, int> dic;
// 输入N行，key为编号i，value为该特性的优先级
for (int i = 1; i <= N; i++) {
int priority;
cin >> priority;
dic[i] = priority;
}
cin.ignore(); // Ignore the newline character after N
// 构建答案哈希表
unordered_map<int, int> ansDic;
// 输入M行
for (int i = 1; i <= M; i++) {
string line;
getline(cin, line);
stringstream ss(line);
// 获得第i个测试用例对应的特性
vector<int> nums;
int num;
while (ss >> num) {
nums.push_back(num);
}
// 将所有特性的优先级进行求和，得到用例i的特性
int sum = 0;
for (int num : nums) {
sum += dic[num];
}
ansDic[i] = sum;
}
// 对所有的id根据优先级大小进行排序，先按照优先级降序排序，优先级相同再按照id大小升序排序
vector<int> ids;
for (const auto& entry : ansDic) {
ids.push_back(entry.first);
}
sort(ids.begin(), ids.end(), [&](int a, int b) {
int diff = ansDic[b] – ansDic[a];
return diff != 0 ? diff < 0 : a < b;
});
// 然后逐行输出
for (int idx : ids) {
cout << idx << endl;
}
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度：O(NM)。在计算每一个测试用例的优先级时，需要遍历最多N个特性，一共有M个用例。
空间复杂度：O(N+M)。两个哈希表所占空间
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
