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

OD统一考试（D卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

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

现在，代号为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

示例1

输入：
2 3 3 1

输出：
5

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

题解

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

解决思路:

实现一个 ok(k) 函数来检查是否可能将员工从1到 ( k ) 分配给国家X和Y。

使用二分查找来找到最小的有效 ( k )。

根据当前的 ( 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;
        }

        // x 、 y 国家都不能分配的员工
        int com = k / (x * y);
        int mx = k / y - com; // 是y的倍数不是x的倍数的人数（可以分配给x国家）
        int my = k / x - com; // 是x的倍数不是y的倍数的人数（可以分配给y国家）

        // 满足x,y 国家的需求还缺少的人数
        int missing = Math.max(0, cntx - mx) + Math.max(0, cnty - my);
		
        // k - mx - my - com 表示既不是x的倍数也不是y的倍数的人数
        return k - mx - my - com >= missing;
    }
}

Python

x, y, cntx, cnty = map(int, input().split())

def ok(k: int) -> bool:
    """  是否可以将编号在[1, k]中的员工分配给X国和y国，且满足x国和y国的需求 """
    global x, y, cntx, cnty
    if k < cntx + cnty:
        return False
	
    # x 、 y 国家都不能分配的员工
    com = k // (x * y)
    # 是y的倍数不是x的倍数的人数（可以分配给x国家）
    # 是x的倍数不是y的倍数的人数（可以分配给y国家）
    mx, my = k // y - com, k // x - com
    
    # 满足x,y 国家的需求还缺少的人数
    missing = max(0, cntx - mx) + max(0, cnty - my)

    # k - mx - my - com 表示既不是x的倍数也不是y的倍数的人数
    return k - mx - my - com >= missing

left, right = 0, 10 ** 15
while left + 1 < right:
    mid = (left + right) // 2
    if ok(mid):
        right = mid
    else:
        left = mid
print(right)

C++

#include <bits/stdc++.h>
using namespace std;

int x, y, cntx, cnty;

// 是否可以将编号在[1, k]中的员工分配给X国和y国，且满足x国和y国的需求
bool ok(int k)
{
    if (k < cntx + cnty) {
        return false;
    }

    int com = k / (x * y);   // x 、 y 国家都不能分配的员工
    int mx  = k / y - com;   // 是y的倍数不是x的倍数的人数（可以分配给x国家）
    int my  = k / x - com;   // 是x的倍数不是y的倍数的人数（可以分配给y国家）

    int missing = max(0, cntx - mx) + max(0, cnty - my);

    return k - mx - my - com >= missing;
}

int main()
{
    cin >> x >> y >> cntx >> cnty;

    long long left  = 0;
    long long right = 1e15;

    while (left + 1 < right) {
        long mid = (left + right) / 2;
        if (ok(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    cout << right;

    return 0;
}