华为OD机试 新系统 统一考试题库清单持续收录中以及考点说明Python/JS/C/C。专栏导读本专栏收录于《华为OD机试真题Python/JS/C/C》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。一、题目描述某校有 n 篇论文需要分配给教师评审。每篇论文 i 可由文件 files[i] 对应的教师列表中任一教师评审。每篇论文至少需要一名教师评审。每位教师 t不论被分配多少篇论文其评审费用固定为 cost[t]。请给出参与评审教师数量最少时的总费用若存在多种方案满足教师数最少则选择总费用最小的方案。二、输入描述第一行输入两个数字空格隔开例如n mn - 论文篇数m - 教师个数接下来的n行是一个二维列表files形式为 files[i][j]:具体内容为- files[0] 允许评审论文 0 的教师列表列表内有多个数值- files[1] 允许评审论文 1 的教师列表- …- files[n-1] 允许评审论文 n − 1 的教师列表最后一行costm个数字逗号隔开分别表示教师编号评审论文的费用例如3 30,11,20,21,2,2表示评审论文0的教师可以为 0,1评审论文1的教师可以为 0,2评审论文2的教师可以为 0,2教师1的费用是1教师2的费用是2教师3的费用是3三、输出描述返回一个整数表示参与教师数量最少时的总费用。约束1 ≤ n ≤ 201 ≤ m ≤ 12files.length 为 nfiles[i] 不为空其中元素满足 0 ≤ files[i][j] mcost[t] 取值 00 t m累计和不超过出整型值范围四、测试用例测试用例11、输入3 30,11,20,21,2,22、输出33、说明评审论文0的教师可以为 0,1评审论文1的教师可以为 0,2评审论文2的教师可以为 0,2教师1的费用是1教师2的费用是2教师3的费用是3方案一编号为 0 和 2 的教师可以完成 3 篇论文评审编号为 0 和 2 的论文分给教师 0编号为 1 的论文分给 2花费是 1 2 3方案二编号 1 和 2 的也可以完成 3 篇评审花费是 2 2 4选择方案一输出3测试用例21、输入3 30121,2,32、输出63、说明n 3m 3 files[[0],[1],[2]]每篇论文只有一个教师可选cost[1,2,3]编号 0,1,2 的教师费用分别为 1,2,3每个论文文档只有一个教师可选所以最小费用是 6五、解题思路由于教师数量 m 12所有教师的选择组合最多只有 2^12 4096 种因此可以直接枚举所有教师子集。对于每一种教师组合判断是否能够覆盖所有论文即每篇论文至少有一名被选择的教师可以评审。如果能够覆盖全部论文则统计当前组合的教师数量和总费用并按照以下优先级更新答案参与教师数量最少如果教师数量相同则选择总费用最小的方案。采用 位掩码BitMask 表示教师集合。例如教师 0、2 可以评审某篇论文则使用二进制101表示。第 t 位为 1代表教师 t 可以评审该论文。使用 int[] fileMasks 保存每篇论文对应的教师集合。判断当前选择的教师能否评审论文 i只需要(subset fileMasks[i]) ! 0这样可以用一次位运算快速判断两个教师集合是否存在交集。六、Python算法源码importsysdefmain():n,mmap(int,sys.stdin.readline().split())file_masks[]for_inrange(n):teachersmap(int,sys.stdin.readline().strip().split(,))mask0# 使用整数的二进制位表示一篇论文允许哪些教师评审。# 第 t 位为 1表示教师 t 可以评审当前论文。forteacherinteachers:mask|1teacher file_masks.append(mask)costlist(map(int,sys.stdin.readline().strip().split(,)))best_countfloat(inf)best_costfloat(inf)# m 12因此教师组合最多只有 4096 种# 可以直接枚举所有非空教师子集。forsubsetinrange(1,1m):# 二进制中 1 的数量就是当前选择的教师人数teacher_countsubset.bit_count()# 第一优先级是教师数量最少ifteacher_countbest_count:continue# 每篇论文的可选教师集合都必须和当前教师集合存在交集。# 如果交集为 0则说明这篇论文没人可以评审。ifany((subsetfile_mask)0forfile_maskinfile_masks):continue# 当前教师组合可以完成全部论文再计算总费用current_costsum(cost[t]fortinrange(m)ifsubset(1t))# 先比较教师人数再比较费用if(teacher_countbest_countor(teacher_countbest_countandcurrent_costbest_cost)):best_countteacher_count best_costcurrent_costprint(best_cost)if__name____main__:main()七、JavaScript算法源码constfsrequire(fs);constlinesfs.readFileSync(0,utf8).trim().split(/\r?\n/);letindex0;const[n,m]lines[index].trim().split(/\s/).map(Number);constfileMasksnewArray(n);for(leti0;in;i){constteacherslines[index].trim().split(,).map(sNumber(s.trim()));letmask0;/* * 使用整数的二进制位记录当前论文允许哪些教师评审。 * * 第 t 位为 1 * 表示教师 t 可以评审当前论文。 */for(constteacherofteachers){mask|(1teacher);}fileMasks[i]mask;}constcostlines[index].trim().split(,).map(sNumber(s.trim()));letbestCountNumber.POSITIVE_INFINITY;letbestCostNumber.POSITIVE_INFINITY;/* * 统计一个整数二进制中 1 的数量。 * * 每次 * x x - 1 * * 都可以删除最低位的一个 1。 */functionbitCount(x){letcount0;while(x!0){x(x-1);count;}returncount;}/* * m 12 * 所有教师组合最多只有 4096 种。 */for(letsubset1;subset(1m);subset){constteacherCountbitCount(subset);// 当前人数已经超过最优人数直接跳过if(teacherCountbestCount){continue;}letcoversAlltrue;/* * 检查所有论文。 * * subset fileMask 0 * 表示当前选择的教师无法评审这篇论文。 */for(constfileMaskoffileMasks){if((subsetfileMask)0){coversAllfalse;break;}}if(!coversAll){continue;}letcurrentCost0;for(lett0;tm;t){if((subset(1t))!0){currentCostcost[t];}}/* * 两层优化目标 * * 第一层教师人数最少 * 第二层人数相同时总费用最低。 */if(teacherCountbestCount||(teacherCountbestCountcurrentCostbestCost)){bestCountteacherCount;bestCostcurrentCost;}}console.log(bestCost);八、C算法源码#includestdio.h#includestring.h#includestdlib.h#includelimits.h/* * 统计整数二进制中 1 的数量。 * * 每执行一次 * x x - 1 * * 就会删除最低位的一个 1。 */intbit_count(intx){intcount0;while(x!0){x(x-1);count;}returncount;}intmain(void){intn,m;scanf(%d %d,n,m);// 读取第一行结尾的换行符getchar();intfileMasks[20]{0};charline[256];/* * 读取每篇论文可以选择的教师。 */for(inti0;in;i){fgets(line,sizeof(line),stdin);intmask0;/* * 使用 strtok 按逗号切分教师编号。 * * 同时使用一个整数的二进制位保存教师集合 * 第 t 位为 1代表教师 t 可以评审当前论文。 */char*tokenstrtok(line,,\r\n);while(token!NULL){intteacheratoi(token);mask|(1teacher);tokenstrtok(NULL,,\r\n);}fileMasks[i]mask;}/* * 读取教师费用 */intcost[12]{0};fgets(line,sizeof(line),stdin);char*tokenstrtok(line,,\r\n);intidx0;while(token!NULLidxm){cost[idx]atoi(token);tokenstrtok(NULL,,\r\n);}intbestCountINT_MAX;longlongbestCostLLONG_MAX;/* * m 12 * 所以最多只有 4096 个教师子集。 * * subset 的第 t 位为 1 * 表示选择教师 t。 */for(intsubset1;subset(1m);subset){intteacherCountbit_count(subset);// 第一优化目标为教师人数最少if(teacherCountbestCount){continue;}intcoversAll1;/* * 检查当前教师集合是否能覆盖所有论文。 */for(inti0;in;i){/* * 交集为 0 * 当前教师组合中没有人可以评审论文 i。 */if((subsetfileMasks[i])0){coversAll0;break;}}if(!coversAll){continue;}/* * 当前组合可以覆盖所有论文 * 计算所有参与教师的固定费用。 */longlongcurrentCost0;for(intt0;tm;t){if((subset(1t))!0){currentCostcost[t];}}/* * 第一关键字教师人数 * 第二关键字总费用。 */if(teacherCountbestCount||(teacherCountbestCountcurrentCostbestCost)){bestCountteacherCount;bestCostcurrentCost;}}printf(%lld\n,bestCost);return0;}九、C算法源码#includeiostream#includesstream#includestring#includevector#includeclimitsusingnamespacestd;intmain(){intn,m;cinnm;// 清除第一行末尾的换行符cin.ignore();vectorintfileMasks(n,0);string line;/* * 读取 n 篇论文对应的教师列表。 */for(inti0;in;i){getline(cin,line);stringstreamss(line);string token;intmask0;/* * 将当前论文允许的教师集合压缩为二进制整数。 * * 例如教师 0、2 可以评审 * * 二进制为 * 101 * * 第 t 位为 1表示教师 t 可以评审。 */while(getline(ss,token,,)){intteacherstoi(token);mask|(1teacher);}fileMasks[i]mask;}/* * 读取费用 */getline(cin,line);stringstreamss(line);string token;vectorintcost;while(getline(ss,token,,)){cost.push_back(stoi(token));}intbestCountINT_MAX;longlongbestCostLLONG_MAX;/* * m 12 * 最多枚举 4096 个教师组合。 */for(intsubset1;subset(1m);subset){/* * __builtin_popcount * 统计整数二进制中 1 的数量 * 即当前选择的教师人数。 */intteacherCount__builtin_popcount((unsigned)subset);if(teacherCountbestCount){continue;}boolcoversAlltrue;/* * 检查每篇论文是否至少存在一个 * 被选中的可评审教师。 */for(intfileMask:fileMasks){if((subsetfileMask)0){coversAllfalse;break;}}if(!coversAll){continue;}longlongcurrentCost0;/* * 一个教师无论评审多少篇论文 * 费用都只计算一次 * 因此直接累加所有被选择教师的费用。 */for(intt0;tm;t){if((subset(1t))!0){currentCostcost[t];}}/* * 优化优先级 * * 1. 教师数量越少越好 * 2. 教师数量相同时费用越低越好。 */if(teacherCountbestCount||(teacherCountbestCountcurrentCostbestCost)){bestCountteacherCount;bestCostcurrentCost;}}coutbestCost\n;return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。
