华为OD机考往年真题 - 员工派遣

2026年在考真题2026年目前正在考的真题目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解文章目录2026年在考真题题目描述输入描述输出描述用例解题思路JavaPython题目描述某公司部门需要派遣员工去国外做项目。现在代号为 x 的国家和代号为 y 的国家分别需要 cntx 名和 cnty 名员工。部门每个员工有一个员工号1,2,3,…工号连续从1开始。部长派遣员工的规则规则1从 [1, k] 中选择员工派遣出去规则2编号为 x 的倍数的员工不能去 x 国编号为 y 的倍数的员工不能去 y 国。问题找到最小的 k使得可以将编号在 [1, k] 中的员工分配给 x 国和 y 国且满足 x 国和 y 国的需求。输入描述四个整数 xycntxcnty。2 ≤ x y ≤ 30000x 和 y 一定是质数1 ≤ cntx, cnty 10^9cntx cnty ≤ 10^9输出描述满足条件的最小的k用例输入2 3 3 1输出5说明输入说明2 表示国家代号23 表示国家代号33 表示国家2需要3个人1 表示国家3需要1个人解题思路题目的问题是要找到一个最小的k使得在遵守上述规则的情况下可以从编号在[1, k]中的员工中选择足够的员工派遣到x国和y国满足他们的需求。输入数据的解释如下2 表示员工的ID如果是2的倍数就不能派遣到国家X。3 表示员工的ID如果是3的倍数就不能派遣到国家Y。3 表示国家X需要3个员工。1 表示国家Y需要1个员工。我们需要找到一个最小的员工ID使得在[1, ID]的范围内能够找到至少3个可以派遣到国家X的员工和至少1个可以派遣到国家Y的员工。在这个例子中员工ID为5是满足条件的最小值。因为在[1, 5]的范围内可以找到3个可以派遣到国家X的员工他们的ID是1, 3, 5以及1个可以派遣到国家Y的员工他的ID是1。所以输出结果是5。这段代码使用了二分查找法Binary Search来寻找满足特定条件的最小员工ID。二分查找法是一种在有序集合中查找特定元素的搜索算法通过每次比较中间元素来缩小搜索范围从而提高查找效率。这里的特定条件是在排除不能同时为两个国家工作的员工后剩余的员工数量能满足两个国家的需求。二分查找法初始化搜索范围下限为两国员工需求之和上限为一个大数例如10亿。在每次循环中计算搜索范围的中间值midStaffID。根据midStaffID判断是否满足条件然后调整搜索范围。如果满足条件缩小上限否则增大下限。重复上述过程直到找到满足条件的最小midStaffID。排除法计算在1到midStaffID范围内不能同时为两个国家工作的员工数量。这些员工的ID是国家X或国家Y的倍数或者两者的公倍数。计算排除这些员工后每个国家实际上还需要多少员工。如果剩余的员工数量能满足两个国家的需求那么midStaffID就满足条件。Javaimportjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);longx,y,cntX,cntY;// 定义静态变量x, y, cntX, cntYxsc.nextLong();// 读取国家X的倍数限制ysc.nextLong();// 读取国家Y的倍数限制cntXsc.nextLong();// 读取国家X需要的员工数量cntYsc.nextLong();// 读取国家Y需要的员工数量longminIDcntXcntY;// 设置员工ID的最小值初值为两国需要的员工总数longmaxID(long)Math.pow(10,18);// 设置员工ID的最大值// 通过二分查找算法找到满足条件的最小员工IDwhile(minIDmaxID){longmidIDminID(maxID-minID)/2;// 计算中间值midIDlongexcludedXmidID/x;// 计算在[1, midID]范围内不能去X国的员工数longexcludedYmidID/y;// 计算在[1, midID]范围内不能去Y国的员工数longexcludedBothmidID/(x*y);// 计算在[1, midID]范围内同时不能去X国和Y国的员工数longneededXMath.max(0,cntX-(excludedY-excludedBoth));// 计算X国实际需要的员工数longneededYMath.max(0,cntY-(excludedX-excludedBoth));// 计算Y国实际需要的员工数longtotalExcludedmidID-excludedX-excludedYexcludedBoth;// 计算总共不能使用的员工数// 判断当前midID是否满足条件if(neededXneededYtotalExcluded){maxIDmidID-1;// 如果满足条件降低最大ID的搜索范围}else{minIDmidID1;// 如果不满足条件提高最小ID的搜索范围}}System.out.println(minID);// 输出满足条件的最小员工IDsc.close();// 关闭扫描器}}Python# 使用map函数和int函数从标准输入读取四个整数x,y,cntX,cntYmap(int,input().split())# minID是满足条件的最小员工ID初始值设置为两个国家需要的员工总数minIDcntXcntY# maxID是员工ID的可能的最大值maxID10**18# 使用二分查找算法whileminIDmaxID:# 计算中间值midIDmidIDminID(maxID-minID)//2# 计算在[1, midID]范围内不能去国家X的员工数量excludedXmidID//x# 计算在[1, midID]范围内不能去国家Y的员工数量excludedYmidID//y# 计算在[1, midID]范围内既不能去X国也不能去Y国的员工数量excludedBothmidID//(x*y)# 计算国家X实际需要的员工数量neededXmax(0,cntX-(excludedY-excludedBoth))# 计算国家Y实际需要的员工数量neededYmax(0,cntY-(excludedX-excludedBoth))# 计算总共不能使用的员工数量totalExcludedmidID-excludedX-excludedYexcludedBoth# 判断当前的中间值是否满足条件ifneededXneededYtotalExcluded:# 如果满足条件则减小最大的搜索范围maxIDmidID-1else:# 如果不满足条件则增加最小的搜索范围minIDmidID1# 输出满足条件的最小员工IDprint(minID)