P2813. 测试用例执行计划

解题思路

又是一道典型的直接看用例比看题意更容易理解的题目。

对于每一个测试用例，ID 都对应一个优先级，而这个优先级的计算是若干特性的优先级的叠加。

假设所有特性对应的优先级已经储存在哈希表 dic 中，dic[num] 表示特性 num 的优先级。

对于特定的测试用例，包含了若干特性的测试 num1, num2, ...，这个测试用例的总优先级为：

最终再进行排序和逐行输出即可。

思路展开 代码分两轮读入、一轮排序输出。第一轮先读入 N 和 M，再用哈希表 dic 逐行记录每个功能点的优先级，dic[i] 表示功能点 i 的优先级，功能点编号从 1 到 N。第二轮读入 M 行测试用例，每行是该用例覆盖的功能点编号列表，用生成器表达式 sum(dic[num] for num in nums) 把这些功能点的优先级累加，作为用例 i 的优先级存入 ans_dic。最后把所有用例 ID 取出，用 lambda 按 (-ans_dic[x], x) 排序：第一关键字取负号实现优先级从高到低，第二关键字是用例 ID 本身，实现优先级相同时 ID 小的先执行。排序后的列表就是执行顺序，逐行输出即可。

复杂度分析 设 N 为功能点个数，M 为测试用例个数，K 为所有测试用例覆盖的功能点编号总数（即 M 行输入里数字的总量）。构建优先级哈希表需要 O(N)；计算所有用例的优先级要把每个覆盖编号各访问一次，共 O(K)；对 M 个用例 ID 排序是 O(M log M)，这也是用例很多时的主要瓶颈。总时间复杂度 O(N + K + M log M)，空间上两个哈希表分别占 O(N) 和 O(M)。

边界与注意事项

• 排序的两个关键字方向相反：优先级要降序、ID 要升序，代码用 -ans_dic[x] 配合默认升序一次完成，两处都不要写反。
• dic[num] 是直接按键访问，依赖"用例覆盖的功能点编号都在 1 到 N 范围内"这一题面设定；编号从 1 开始，构建 dic 的循环用的是 range(1, N+1)，不要写成从 0 开始。
• 某个用例只覆盖一个功能点时，求和退化为单个值，代码不需要特殊处理。