华为OD机试 - 最小代价完成论文评审 - 二进制（Java 新系统 100分）

华为OD机试 新系统 题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。一、题目描述某校有 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这样可以用一次位运算快速判断两个教师集合是否存在交集。六、Java算法源码publicclassOdTest{publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);intnscanner.nextInt();// 论文数量intmscanner.nextInt();// 教师数量scanner.nextLine();// 消耗第一行末尾的换行符int[]fileMasksnewint[n];for(inti0;in;i){Stringlinescanner.nextLine().trim();String[]partsline.split(,);/* * 使用一个整数的二进制位表示当前论文允许哪些教师评审。 * * 例如 * 教师 0 和教师 2 可以评审 * 二进制表示就是 101。 * * 第 t 位为 1代表教师 t 可以评审当前论文。 */intmask0;for(Stringpart:parts){intteacherInteger.parseInt(part.trim());mask|(1teacher);}fileMasks[i]mask;}String[]costPartsscanner.nextLine().trim().split(,);int[]costnewint[m];for(inti0;im;i){cost[i]Integer.parseInt(costParts[i].trim());}intbestTeacherCountInteger.MAX_VALUE;longbestCostLong.MAX_VALUE;/* * m 12因此教师所有组合最多 * * 2^12 4096 * * 可以直接枚举所有教师子集。 * * subset 的第 t 位为 1 * 表示教师 t 被选择参与评审。 */inttotalSubsets1m;// 空集合一定无法评审论文所以从 1 开始枚举for(intsubset1;subsettotalSubsets;subset){// subset 中二进制 1 的数量就是当前参与教师数量intteacherCountInteger.bitCount(subset);/* * 第一优化目标是教师人数最少。 * * 如果当前教师人数已经超过目前最优人数 * 无论费用是多少都不可能成为答案。 */if(teacherCountbestTeacherCount){continue;}booleancoversAlltrue;/* * 检查当前教师组合能否覆盖所有论文。 * * subset fileMasks[i] 0 * 表示当前选择的教师与论文 i 可以选择的教师没有交集。 * * 也就是没人能够评审这篇论文。 */for(inti0;in;i){if((subsetfileMasks[i])0){coversAllfalse;break;}}if(!coversAll){continue;}// 当前组合可以覆盖全部论文计算参与教师的固定费用longcurrentCost0;for(intt0;tm;t){if((subset(1t))!0){currentCostcost[t];}}/* * 按照两个优先级更新答案 * * 1. 教师数量更少直接更新 * 2. 教师数量相同则选择总费用更小的方案。 */if(teacherCountbestTeacherCount||(teacherCountbestTeacherCountcurrentCostbestCost)){bestTeacherCountteacherCount;bestCostcurrentCost;}}System.out.println(bestCost);scanner.close();}}七、效果展示1、输入4 40,10,21,32,35,2,3,12、输出53、说明存在两个只使用 2 位教师的方案。方案一{0,3}费用5 1 6方案二{1,2}费用2 3 5两种方案教师人数相同因此选择费用更低的5下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。