目录

题目

思路

Code

题目

题目内容：

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

每篇论文 i 可由 files[i] 对应的教师列表中任一教师评审。

每篇论文至少需要一名教师评审。

每位教师 t 不论被分配多少篇论文，其评审费用固定为 cost[t]。

请给出参与评审教师数量最少时的总费用。

如果存在多种方案满足教师数量最少，则选择总费用最小的方案。

输入描述：

第一行输入 n 和 m，表示论文篇数和教师个数；也可以分两行分别输入 n 和 m。

接下来 n 行，每行是逗号分隔的教师编号列表，表示该论文可选教师。

最后一行是逗号分隔的 cost 数组，cost[t] 表示教师 t 的固定费用。

n 的范围为 1 到 20。

m 的范围为 1 到 12。

files 长度为 n，且每个 files[i] 非空，教师编号范围为 0 到 m-1。

cost[t] 为正整数，累计费用不超过整型范围。

输出描述：

输出参与教师数量最少时的最小总费用。

样例 1

输入：

3
3
0,1
1,2
0,2
1,2,2

输出：

3

说明：

选择教师 0 和 2 可以覆盖三篇论文，教师数量为 2，总费用为 3。

样例 2

输入：

3 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

说明：

可以选择教师 3 和 4 覆盖全部论文，费用为 6；也可以选择 0、1、2 覆盖，教师数更多。按教师数量优先，再比较费用。

思路

整体思路：教师数量最多 12，可以枚举所有教师子集，判断能否覆盖所有论文。

第一步：把每篇论文的候选教师列表保留下来，把每个教师子集看成一个二进制掩码。

第二步：对每个掩码检查所有论文，若某篇论文没有任何候选教师在掩码中，则该掩码不可用。

第三步：可用掩码计算教师数量和费用，先比较教师数量，再比较费用。

第四步：遍历结束后输出最优费用。

边界处理：因为每篇论文至少有候选教师，选择全部教师一定能覆盖所有论文。

复杂度分析：共有 2 的 m 次方个教师集合，每个集合检查 n 篇论文，时间复杂度为 O(2^m * n * c)，空间复杂度为 O(n * c)。

Code

import sys

lines = [line.strip() for line in sys.stdin.read().splitlines() if line.strip()]
if not lines:
    sys.exit()
# 兼容 n m 同行或 n、m 分两行两种输入写法。
first = lines[0].replace(",", " ").split()
if len(first) >= 2:
    n, m = map(int, first[:2])
    pos = 1
else:
    n = int(first[0])
    m = int(lines[1])
    pos = 2
files = []
for _ in range(n):
    # 每篇论文一行，逗号分隔可评审它的教师编号。
    files.append([int(x) for x in lines[pos].split(",") if x != ""])
    pos += 1
cost = [int(x) for x in lines[pos].split(",") if x != ""]

best_count = m + 1
best_cost = 10 ** 18
# m 不超过 12，枚举教师集合比搜索分配方案更直接。
for mask in range(1, 1 << m):
    selected = bin(mask).count("1")
    # 教师数已经劣于当前最优时，不必再检查覆盖和费用。
    if selected > best_count:
        continue
    ok = True
    for teachers in files:
        # 当前教师集合必须和每篇论文的候选教师有交集。
        if not any(mask & (1 << t) for t in teachers):
            ok = False
            break
    if not ok:
        continue
    # 教师费用是固定成本，同一教师无论评几篇论文只算一次。
    total = sum(cost[t] for t in range(m) if mask & (1 << t))
    # 先最小化教师数量，再在同数量中选择最低费用。
    if selected < best_count or (selected == best_count and total < best_cost):
        best_count = selected
        best_cost = total
print(best_cost)

JS

const fs = require("fs");

const lines = fs.readFileSync(0, "utf8").split(/\r?\n/).map(s => s.trim()).filter(Boolean);
// 兼容 n m 同行或 n、m 分两行输入。
const first = lines[0].replace(/,/g, " ").split(/\s+/).map(Number);
let n = first[0];
let m, pos;
if (first.length >= 2) {
  m = first[1];
  pos = 1;
} else {
  m = Number(lines[1]);
  pos = 2;
}
const files = [];
for (let i = 0; i < n; i++, pos++) {
  // 每篇论文保存可评审它的教师编号列表。
  files.push(lines[pos].split(",").filter(Boolean).map(Number));
}
const cost = lines[pos].split(",").filter(Boolean).map(Number);
let bestCount = m + 1;
let bestCost = Number.MAX_SAFE_INTEGER;
// 教师数量最多 12，枚举子集比枚举论文分配更简单。
for (let mask = 1; mask < (1 << m); mask++) {
  const selected = mask.toString(2).split("1").length - 1;
  // 教师数已经劣于当前答案时，直接跳过。
  if (selected > bestCount) continue;
  let ok = true;
  for (const teachers of files) {
    // 任一候选教师被选中即可覆盖当前论文。
    if (!teachers.some(t => (mask & (1 << t)) !== 0)) {
      ok = false;
      break;
    }
  }
  if (!ok) continue;
  // 固定费用只按参与教师求和一次。
  let total = 0;
  for (let t = 0; t < m; t++) if ((mask & (1 << t)) !== 0) total += cost[t];
  // 教师数量相同的时候，固定费用更小的集合更优。
  if (selected < bestCount || (selected === bestCount && total < bestCost)) {
    bestCount = selected;
    bestCost = total;
  }
}
console.log(bestCost);

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。