华为OD机试：员工派遣

题目描述

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

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

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

部长派遣员工的规则：

问题：

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

输入描述

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

输出描述

满足条件的最小的k

用例

题目解析

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

2.根据规则2，我们知道编号为x的倍数的员工不能去x国，编号为y的倍数的员工不能去y国。因此，我们可以先计算出每个国家可以派遣的员工数量。

3.对于x国，我们可以从1到k中选择员工，但是需要排除掉编号为x的倍数的员工。同样地，对于y国，我们可以从1到k中选择员工，但是需要排除掉编号为y的倍数的员工。

4.接下来，我们可以通过比较x国和y国可以派遣的员工数量与实际需求的差异来确定最小的k。如果x国可以派遣的员工数量小于cntx，说明k还太小，需要增大k；如果y国可以派遣的员工数量小于cnty，说明k还太小，需要增大k。

5.我们可以通过二分查找的方式来逐步缩小k的范围，直到找到满足条件的最小的k。

JS算法源码
const rl = require("readline").createInterface({ input: process.stdin });
const iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

(async function () {
  const [x, y, cntx, cnty] = (await readline()).split(" ").map(Number);

  const check = k => {
    const A = Math.floor(k / x); 
    const B = Math.floor(k / y);  
    const C = Math.floor(k / (x * y));  
    return (
      Math.max(0, cntx - (B - C)) + Math.max(0, cnty - (A - C)) <= k - A - B + C
    );
  }

  let min = cntx + cnty;
  let max = 1e9;  
  while (min <= max) {
    let mid = min + Math.floor((max - min) / 2);

    if (check(mid)) {
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }

  console.log(min);
})();

Java算法源码
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long x = sc.nextLong();
        long y = sc.nextLong();
        long cntx = sc.nextLong();
        long cnty = sc.nextLong();

        long min = cntx + cnty;
        long max = 1000000000L;

        while (min <= max) {
            long mid = min + (max - min) / 2;

            if (check(mid, x, y, cntx, cnty)) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        System.out.println(min);
    }

    public static boolean check(long k, long x, long y, long cntx, long cnty) {
        long A = k / x;
        long B = k / y;
        long C = k / (x * y);

        return Math.max(0, cntx - (B - C)) + Math.max(0, cnty - (A - C)) <= k - A - B + C;
    }
}

Python算法源码
 
import sys

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

def check(k):
    A, B = divmod(k, x)
    C, _ = divmod(k, y)
    return max(0, cntx - (B - C)) + max(0, cnty - (A - C)) <= k - A - B + C

def getResult():
    low = cntx + cnty
    high = 1000000000

    while low < high:
        mid = (low + high) // 2

        if check(mid):
            high = mid
        else:
            low = mid + 1

    return low

print(getResult())

C算法源码
#include <iostream>
#include <algorithm>

long long x, y, cntx, cnty;

bool check(long long k) {
    long long A = k / x;
    long long B = k / y;
    long long C = k / (x * y);
    return std::max(0LL, cntx - (B - C)) + std::max(0LL, cnty - (A - C)) <= k - A - B + C;
}

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

    long long min = cntx + cnty;
    long long max = 1e9;

    while (min <= max) {
        long long mid = min + (max - min) / 2;

        if (check(mid)) {
            max = mid - 1;
        } else {
            min = mid + 1;
        }
    }

    std::cout << min << std::endl;

    return 0;
}