2026 华为OD机试真题 7月22日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

某校有 n 篇论文需要分配给教师评审。

• 每篇论文 i 可由文件 files[i] 对应的教师列表中任一教师评审。
• 每篇论文至少需要一名教师评审。
• 每位教师 t，不论被分配多少篇论文，其评审费用固定为 cost[t]。

请给出参与评审教师数量最少时的总费用；若存在多种方案满足教师数最少，则选择总费用最小的方案。

2026 华为OD机试真题 7月22日华为OD上机新系统考试真题 100 分题型

输入描述

输入，共有 4 个：

• n - 论文篇数

• m - 教师个数

• files - 二维列表，形式为 files[i][j]

  具体内容为：

  • files[0] 允许评审论文 0 的教师列表，列表内有多个数值
  • files[1] 允许评审论文 1 的教师列表
  • ...
  • files[n-1] 允许评审论文 n−1 的教师列表

• cost - 一维列表，列表索引 t 表示教师编号 t，列表值表示对应教师编号评审论文的费用

输出描述

返回一个整数，表示参与教师数量最少时的总费用。

约束

• 1≤n≤20
• 1≤m≤12
• files.length 为 n，files[i] 不为空，其中元素满足 0≤files[i][j]\<m
• cost[t] 取值 >0，0≤t<m，累计和不超过整型值范围

示例1

输入

3,3,[[0,1],[1,2],[0,2]],[1,2,2]

输出

3

说明

• n=3，m=3，files=[[0,1],[1,2],[0,2]]，cost=[1,2,2]，min_cost=3
• 方案一：编号为 0 和 2 的教师可以完成 3 篇论文评审，编号为 0 和 2 的论文分给教师 0，编号为 1 的论文分给 2，花费是 1+2=3
• 方案二：编号 1 和 2 的也可以完成 3 篇评审，花费是 2+2=4
• 所以选择方案一，最小费用是 3。

示例2

输入

3,3,[[0],[1],[2]],[1,2,3]

输出

6

说明

• n=3，m=3，files=[[0],[1],[2]]，每篇论文只有一个教师可选
• cost=[1,2,3]，编号 0,1,2 的教师费用分别为 1,2,3
• 每个论文文档只有一个教师可选，所以最小费用是 6。

示例3

输入

4,5,[[0,3,4],[1,3],[2,4],[0,4]],[1,1,1,3,3]

输出

4

说明

输入：

• n=4，m=5
• files=[[0,3,4],[1,3],[2,4],[0,4]]
• cost=[1,1,1,3,3]

覆盖关系：

• 教师 0→ 论文 [0,3]，费用 1
• 教师 1→ 论文 [1]，费用 1
• 教师 2→ 论文 [2]，费用 1
• 教师 3→ 论文 [0,1]，费用 3
• 教师 4→ 论文 [0,2,3]，费用 3

方案对比：

• 3 名教师 [0,1,2] 覆盖全部，费用 =3 / 教师多，费用少
• 2 名教师 [1,4] 覆盖全部，费用 =4 教师少，费用次优
• 2 名教师 [3,4] 覆盖全部，费用 =6

输出：4

解释：方案 [0,1,2] 用 3 名教师仅花费 3，比 [1,4] 的 4 更便宜，但因教师数量为 3（多于 2）。按“教师最少优先”原则淘汰该法。最终选 2 名教师的方案，在 [1,4] 和 [3,4] 中取费用最小的 4。

解题思路

核心思想

教师数量最多为 12，可以枚举所有教师集合。对每个集合判断它能覆盖哪些论文：只要某篇论文允许的教师中有一个在当前集合里，这篇论文就能被评审。

题目的优化目标有优先级：先让参与教师数量最少；教师数量相同时，再让总费用最小。因此枚举集合时同时维护两个指标即可。

算法步骤

1. 按示例格式读取一行输入，解析出 n、m、二维列表 files 和费用列表 cost。
2. 预处理每位教师能够评审的论文集合，用二进制位表示：第 i 位为 1 表示可以覆盖论文 i。
3. 枚举所有教师集合 mask，范围为 到 2^m - 1。
4. 对集合中的每位教师，合并其论文覆盖状态，并累加费用。
5. 如果当前集合能覆盖全部论文，则比较：
   • 教师数量更少，直接更新答案。
   • 教师数量相同，费用更少时更新答案。
6. 枚举结束后输出最优费用。

复杂度分析

设教师数量为 m，论文数量为 n。

• 预处理教师覆盖集合的复杂度为 O(n * k)，其中 k 为所有 files[i] 列表长度总和。
• 枚举 2^m 个教师集合，每个集合最多遍历 m 位，时间复杂度为 O(2^m * m)。
• 额外保存每位教师覆盖论文的二进制状态，空间复杂度为 `O(