华为od机试真题：测试用例执行计划(C语言)

2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

某个产品当前迭代周期内有N个特性（F1, F2, ..., FN）需要进行覆盖测试，每个特性都被评估了对应的优先级，特性使用其ID作为下标进行标识。

设计了M个测试用例（T1, T2,...,TM），每个用例对应了一个覆盖特性的集合，测试用例使用其ID作为下标进行标识，测试用例的优先级定义为其覆盖的特性的优先级之和。

在开展测试之前，需要制定测试用例的执行顺序，规则为：优先级大的用例先执行，如果存在优先级相同的用例，用例ID小的先执行。

输入描述

第一行输入为N和M，N表示特性的数量，M表示测试用例的数量。

之后N行表示特性ID=1到特性ID=N的优先级。

再接下来M行表示测试用例ID=1到测试用例ID=M关联的特性的ID的列表。

输出描述

按照执行顺序（优先级从大到小）输出测试用例的ID，每行一个ID。

示例1

输入
5 4
1
1
2
3
5
1 2 3
1 4
3 4 5
2 3 4

输出
3
4
1
2

示例2

输入
3 3
3
1
5
1 2 3
1 2 3
1 2 3

输出
1
2
3

题解

题目类型

这道题属于 贪心算法 的问题，通过优先级排序的方式来决定测试用例的执行顺序。

解题思路

1. 输入解析：
   • 首先读取特性的数量 N 和测试用例的数量 M。
   • 接着读取每个特性的优先级，将其存储在数组中。
   • 对于每个测试用例，读取其关联的特性列表，计算该测试用例的总优先级（所有关联特性的优先级之和）。
2. 贪心策略：
   • 根据测试用例的优先级对测试用例进行排序，优先级高的用例优先执行。
   • 如果两个测试用例的优先级相同，则按照用例ID的顺序从小到大执行。
3. 排序和输出：
   • 利用排序函数（比如 qsort），按照优先级从大到小进行排序。
   • 输出排序后的测试用例ID。

代码大致描述

• 通过结构体 Case 存储测试用例的ID和对应的优先级。
• 读取每个测试用例的关联特性并计算优先级总和。
• 使用 qsort 对测试用例按优先级排序，优先级相同的按ID从小到大排序。
• 最终按顺序输出测试用例ID。

时间复杂度

• 时间复杂度：主要是排序的时间复杂度，即 O(M log M)，其中 M 是测试用例的数量。计算每个测试用例优先级的时间复杂度为 O(N * M)，总的时间复杂度是 O(M * N + M log M)。
• 空间复杂度：使用了数组来存储特性优先级和测试用例，空间复杂度为 O(N + M)。

C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int t;  // 测试用例优先级
    int id; // 测试用例 ID
} Case;

// const void* 是一个指向常量 void 类型的指针。它用于指向任意类型的数据。
// 在 qsort 函数中，比较函数的参数类型必须是 const void*，以便能够通用地处理任意类型的数据。
int cmp(const void *_a, const void *_b) {
    Case *a = (Case *) _a;
    Case *b = (Case *) _b;
    return (a->t == b->t) ? a->id - b->id : b->t - a->t;
}

int main(void) {
    int n, m;
    scanf("%d %d", &n, &m);

    // 存储每个特性的优先级，索引下标特性ID，值是优先级
    int p[n];
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);

    Case cases[m];
    // 读取 m 个测试用例
    for (int i = 1; i <= m; i++) {
        for (int t = 0, x = 0; ;) {
            scanf("%d", &x);
            t += p[x - 1];

            // 读到行的末尾
            if (getchar() == '\n') {
                cases[i].id = i;
                cases[i].t = t;
                break;
            }
        }
    }

    // 对测试用例进行排序
    qsort(cases, m, sizeof(Case), cmp);

    // 打印结果
    for (int i = 0; i < m; i++) printf("%d\n", cases[i].id);

    return 0;
}

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 收藏 ⭐和小红花🌹，让更多的人看到。🙏🙏🙏