最新华为OD机试真题-LYA的测试用例执行计划(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🎀 LYA的测试用例执行计划
问题描述
LYA是一名软件测试工程师,她需要为当前迭代周期内的 个特性 设计测试用例。每个特性都有一个优先级,特性用它的编号 来表示。
LYA设计了 个测试用例 ,每个测试用例覆盖了一些特性。测试用例的优先级定义为它所覆盖的所有特性的优先级之和。
在开始测试之前,LYA需要安排这 个测试用例的执行顺序。她希望优先级高的测试用例先执行。如果两个测试用例的优先级相同,那么编号较小的测试用例先执行。
请你帮助LYA生成这个测试用例的执行计划。
输入格式
第一行包含两个正整数 和 ,分别表示特性的数量和测试用例的数量。
接下来 行,每行一个整数,第 行的整数表示特性 的优先级。
再接下来 行,每行若干个整数,表示一个测试用例覆盖的特性的编号。
- 每个特性的优先级是不超过 的正整数
- 每个测试用例覆盖的特性编号互不相同
输出格式
输出 行,每行一个整数,表示测试用例的执行顺序。
样例输入
5 4
1
1
2
3
5
1 2 3
1 4
3 4 5
2 3 4
样例输出
3
4
1
2
样例解释
测试用例的优先级计算如下:
- 覆盖特性 ,优先级为
- 覆盖特性 ,优先级为
- 覆盖特性 ,优先级为
- 覆盖特性 ,优先级为
按照优先级从高到低,优先级相同时按编号从小到大的顺序,测试用例的执行顺序应该是 。
样例输入
3 3
3
1
5
1 2 3
1 2 3
1 2 3
样例输出
1
2
3
样例解释
三个测试用例的优先级都是 ,所以按照编号从小到大的顺序执行。
数据范围
- 每个特性的优先级
题解
本题可以用排序来解决。
首先,我们可以计算出每个测试用例的优先级。具体做法是,遍历每个测试用例覆盖的特性,将这些特性的优先级累加起来,就得到了这个测试用例的优先级。
然后,我们可以将测试用例按照优先级从高到低排序。如果两个测试用例的优先级相同,就按照编号从小到大排序。
最后,我们按照排序后的顺序,依次输出每个测试用例的编号,就得到了最终的执行计划。
时间复杂度分析:计算每个测试用例的优先级需要 的时间,排序需要 的时间,输出结果需要 的时间。因此,总时间复杂度是 。
参考代码
- Python
n, m = map(int, input().split())
priority = [int(input()) for _ in range(n)]
test_cases = []
for i in range(m):
features = list(map(int, input().split()))
p = sum(priority[f - 1] for f in features)
test_cases.append((p, i + 1))
test_cases.sort(key=lambda x: (-x[0], x[1]))
for _, id in test_cases:
print(id)
- Java
import java.util.*;
public class Main {
public static void main(String[] args
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测