【2024最新华为OD-C/D卷试题汇总】[支持在线评测] LYA的测试用例执行计划(100分) - 三语言AC题解(Python/Java/Cpp)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1069
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

🎀 LYA的测试用例执行计划

问题描述

LYA是一名软件测试工程师,她需要为当前迭代周期内的 $N$ 个特性 $(F_1,F_2,\dots ,F_N)$ 设计测试用例。每个特性都有一个优先级,特性用它的编号 $i$ 来表示。

LYA设计了 $M$ 个测试用例 $(T_1,T_2,\dots ,T_M)$,每个测试用例覆盖了一些特性。测试用例的优先级定义为它所覆盖的所有特性的优先级之和。

在开始测试之前,LYA需要安排这 $M$ 个测试用例的执行顺序。她希望优先级高的测试用例先执行。如果两个测试用例的优先级相同,那么编号较小的测试用例先执行。

请你帮助LYA生成这个测试用例的执行计划。

输入格式

第一行包含两个正整数 $N$ 和 $M$,分别表示特性的数量和测试用例的数量。

接下来 $N$ 行,每行一个整数,第 $i$ 行的整数表示特性 $F_i$ 的优先级。

再接下来 $M$ 行,每行若干个整数,表示一个测试用例覆盖的特性的编号。

• $1\le N,M\le 100$
• 每个特性的优先级是不超过 $10^9$ 的正整数
• 每个测试用例覆盖的特性编号互不相同

输出格式

输出 $M$ 行,每行一个整数,表示测试用例的执行顺序。

样例输入

5 4
1
1
2
3
5
1 2 3
1 4
3 4 5
2 3 4

样例输出

3
4
1
2

样例解释

测试用例的优先级计算如下：

• $T_1$ 覆盖特性 $F_1,F_2,F_3$,优先级为 $1+1+2=4$
• $T_2$ 覆盖特性 $F_1,F_4$,优先级为 $1+3=4$
• $T_3$ 覆盖特性 $F_3,F_4,F_5$,优先级为 $2+3+5=10$
• $T_4$ 覆盖特性 $F_2,F_3,F_4$,优先级为 $1+2+3=6$

按照优先级从高到低,优先级相同时按编号从小到大的顺序,测试用例的执行顺序应该是 $T_3,T_4,T_1,T_2$。

样例输入

3 3
3
1
5
1 2 3
1 2 3
1 2 3

样例输出

1
2
3

样例解释

三个测试用例的优先级都是 $3+1+5=9$,所以按照编号从小到大的顺序执行。

数据范围

• $1\le N,M\le 100$
• $1\le$ 每个特性的优先级 $\le 10^9$

题解

本题可以用排序来解决。

首先,我们可以计算出每个测试用例的优先级。具体做法是,遍历每个测试用例覆盖的特性,将这些特性的优先级累加起来,就得到了这个测试用例的优先级。

然后,我们可以将测试用例按照优先级从高到低排序。如果两个测试用例的优先级相同,就按照编号从小到大排序。

最后,我们按照排序后的顺序,依次输出每个测试用例的编号,就得到了最终的执行计划。

时间复杂度分析:计算每个测试用例的优先级需要 $O(NM)$ 的时间,排序需要 $O(M\log M)$ 的时间,输出结果需要 $O(M)$ 的时间。因此,总时间复杂度是 $O(NM+M\log M)$。

参考代码

• 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) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[] priority = new int[n];for (int i = 0; i < n; i++) {priority[i] = in.nextInt();}List<TestCase> testCases = new ArrayList<>();in.nextLine(); // consume the remaining newlinefor (int i = 0; i < m; i++) {String line = in.nextLine();String[] features = line.split(" ");int p = 0;for (String feature : features) {p += priority[Integer.parseInt(feature) - 1];}testCases.add(new TestCase(p, i + 1));}testCases.sort((a, b) -> {if (a.priority != b.priority) {return b.priority - a.priority;}return a.id - b.id;});for (TestCase testCase : testCases) {System.out.println(testCase.id);}}static class TestCase {int priority;int id;TestCase(int priority, int id) {this.priority = priority;this.id = id;}}
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n, m;cin >> n >> m;vector<int> priority(n);for (int i = 0; i < n; i++) {cin >> priority[i];}vector<pair<int, int>> testCases;for (int i = 0; i < m; i++) {int feature;int p = 0;while (cin >> feature) {p += priority[feature - 1];if (cin.get() == '\n') {break;}}testCases.emplace_back(p, i + 1);}sort(testCases.begin(), testCases.end(), [](const auto& a, const auto& b) {if (a.first != b.first) {return a.first > b.first;}return a.second < b.second;});for (const auto& testCase : testCases) {cout << testCase.second << endl;}return 0;
}