员工派遣 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 200分

题解： Java / Python / 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一定是质数;)

输出描述

满足条件的最小的k

示例1

输入：
2 3 3 1

输出：
5

说明：
2 表示国家代号2
3 表示国家代号3
3 表示国家2需要3个人
1 表示国家3需要1个人

题解

这个问题可以归类为二分查找问题。目标是找到最小的 ( k )，使得员工的编号从1到 ( k ) 可以被分配到国家X和Y，并满足它们的需求。

解决思路:

1. 实现一个 ok(k) 函数来检查是否可能将员工从1到 ( k ) 分配给国家X和Y。
2. 使用二分查找来找到最小的有效 ( k )。
3. 根据当前的 ( k ) 是否满足条件，调整搜索范围。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class EmployeeDistribution {
    static int x, y, cntx, cnty;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        x = sc.nextInt();
        y = sc.nextInt();
        cntx = sc.nextInt();
        cnty = sc.nextInt();

        int left = 0;
        int right = Integer.MAX_VALUE;

        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (ok(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        System.out.println(right);
    }

    public static boolean ok(int k) {
        if (k < cntx + cnty) {
            return false;
        }