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

2026年在考真题

2026年目前正在考的真题目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

某公司部门需要派遣员工去国外做项目。

现在，代号为 x 的国家和代号为 y 的国家分别需要 cntx 名和 cnty 名员工。

部门每个员工有一个员工号（1,2,3,…），工号连续，从1开始。

部长派遣员工的规则：

• 规则1：从 [1, k] 中选择员工派遣出去
• 规则2：编号为 x 的倍数的员工不能去 x 国，编号为 y 的倍数的员工不能去 y 国。

问题：

找到最小的 k，使得可以将编号在 [1, k] 中的员工分配给 x 国和 y 国，且满足 x 国和 y 国的需求。

输入描述

四个整数 x，y，cntx，cnty。

• 2 ≤ x < y ≤ 30000
• x 和 y 一定是质数
• 1 ≤ cntx, cnty < 10^9
• cntx + cnty ≤ 10^9

输出描述

满足条件的最小的k

用例

解题思路

题目的问题是：要找到一个最小的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。二分查找法是一种在有序集合中查找特定元素的搜索算法，通过每次比较中间元素来缩小搜索范围，从而提高查找效率。

这里的特定条件是：在排除不能同时为两个国家工作的员工后，剩余的员工数量能满足两个国家的需求。

1. 二分查找法：

   • 初始化搜索范围，下限为两国员工需求之和，上限为一个大数（例如10亿）。
   • 在每次循环中，计算搜索范围的中间值midStaffID。
   • 根据midStaffID判断是否满足条件，然后调整搜索范围。如果满足条件，缩小上限；否则，增大下限。
   • 重复上述过程，直到找到满足条件的最小midStaffID。

2. 排除法：

   • 计算在1到midStaffID范围内，不能同时为两个国家工作的员工数量。
   • 这些员工的ID是国家X或国家Y的倍数，或者两者的公倍数。
   • 计算排除这些员工后，每个国家实际上还需要多少员工。
   • 如果剩余的员工数量能满足两个国家的需求，那么midStaffID就满足条件。

Java

importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);longx,y,cntX,cntY;// 定义静态变量x, y, cntX, cntYx=sc.nextLong();// 读取国家X的倍数限制y=sc.nextLong();// 读取国家Y的倍数限制cntX=sc.nextLong();// 读取国家X需要的员工数量cntY=sc.nextLong();// 读取国家Y需要的员工数量longminID=cntX+cntY;// 设置员工ID的最小值，初值为两国需要的员工总数longmaxID=(long)Math.pow(10,18);// 设置员工ID的最大值// 通过二分查找算法找到满足条件的最小员工IDwhile(minID<=maxID){longmidID=minID+(maxID-minID)/2;// 计算中间值midIDlongexcludedX=midID/x;// 计算在[1, midID]范围内不能去X国的员工数longexcludedY=midID/y;// 计算在[1, midID]范围内不能去Y国的员工数longexcludedBoth=midID/(x*y);// 计算在[1, midID]范围内同时不能去X国和Y国的员工数longneededX=Math.max(0,cntX-(excludedY-excludedBoth));// 计算X国实际需要的员工数longneededY=Math.max(0,cntY-(excludedX-excludedBoth));// 计算Y国实际需要的员工数longtotalExcluded=midID-excludedX-excludedY+excludedBoth;// 计算总共不能使用的员工数// 判断当前midID是否满足条件if(neededX+neededY<=totalExcluded){maxID=midID-1;// 如果满足条件，降低最大ID的搜索范围}else{minID=midID+1;// 如果不满足条件，提高最小ID的搜索范围}}System.out.println(minID);// 输出满足条件的最小员工IDsc.close();// 关闭扫描器}}

Python

# 使用map函数和int函数从标准输入读取四个整数x,y,cntX,cntY=map(int,input().split())# minID是满足条件的最小员工ID，初始值设置为两个国家需要的员工总数minID=cntX+cntY# maxID是员工ID的可能的最大值maxID=10**18# 使用二分查找算法whileminID<=maxID:# 计算中间值midIDmidID=minID+(maxID-minID)//2# 计算在[1, midID]范围内不能去国家X的员工数量excludedX=midID//x# 计算在[1, midID]范围内不能去国家Y的员工数量excludedY=midID//y# 计算在[1, midID]范围内既不能去X国也不能去Y国的员工数量excludedBoth=midID//(x*y)# 计算国家X实际需要的员工数量neededX=max(0,cntX-(excludedY-excludedBoth))# 计算国家Y实际需要的员工数量neededY=max(0,cntY-(excludedX-excludedBoth))# 计算总共不能使用的员工数量totalExcluded=midID-excludedX-excludedY+excludedBoth# 判断当前的中间值是否满足条件ifneededX+neededY<=totalExcluded:# 如果满足条件，则减小最大的搜索范围maxID=midID-1else:# 如果不满足条件，则增加最小的搜索范围minID=midID+1# 输出满足条件的最小员工IDprint(minID)