返回目录

题目描述

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

现在，代号为 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\~k 范围内，x的倍数的数量该如何求解。

比如 1\~10 范围内，2的倍数有：2,4,6,8,10，共计5个

比如 1\~20 范围内，3的倍数有：3,6,9,12,15,18，共计6个

可以发现1\~k范围内x的倍数的个数 = k // x，其中//表示整除。

证明也很简单，大家可以自行验证。

因此，我们可以得出1\~k范围内：

• x的倍数个数有：k // x 个，假设 A = k // x
• y的倍数个数有：k // y 个，假设 B = k // y

同时，我们还需要关注 1\~k 范围内：

• x*y的倍数的个数有： k // (x*y) 个，假设 = C // (x*y)

即 1 \~ k 范围内：

• x倍数且非y倍数的个数有：A - C 个
• y倍数且非x倍数的个数有：B - C 个

我们可以让：

• “x倍数且非y倍数” 的数去 y 国
• "y倍数且非x倍数" 的数去 x 国

那么此时

• x 国还差：max(0, cntx - (B-C)) 个
• y 国还差：max(0, cnty - (A-C)) 个

而差的人可以从 1\~k 范围内，非x倍数也非y倍数的数中选，而

• 非x倍数也非y倍数的值得数量有：k - A - B + C

因此，只要k满足下面不等式即可：

max(0, cntx - (B-C)) + max(0, cnty - (A-C)) ≤ k - A - B + C

由于是不等式，因此我们无法直接计算出k的值，这里我们可以通过二分法取中间值作为k的可能值，带入上面不等式，

• 如果满足，则对应k是一个可能解，我们继续尝试更小的k，即下一轮缩小二分右边界
• 如果不满足，则说明k值取小了，下一轮应该扩大二分左边界，尝试更大的k

而k的二分范围，即k的可能取值范围是：

• k至少是 cntx+cnty，即 1\~k号员工可以分两拨，一波cntx个且保证非x倍数，一波cnty个且保证非y倍数
• k至多是一个整型最大值（想了几个最大值计算公式，感觉不保险，这里还是用一个Long.MAX\_VALUE比较保险，反正这个上限往大了搞就行）

Python算法源码

import math

def check(k, x, y, cntx, cnty):
    # 1~k范围内x倍数的数量
    A = k // x  
    # 1~k范围内y倍数的数量
    B = k // y  
    # 1~k范围内x*y倍数的数量
    C = k // (x * y)  

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

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

    min_val = cntx + cnty
    max_val = 1000000000

    while min_val <= max_val:
        mid = min_val + (max_val - min_val) // 2

        if check(mid, x, y, cntx, cnty):
            max_val = mid - 1
        else:
            min_val = mid + 1

    print(min_val)

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

int x, y, cntX, cntY;

int handle(int persons) {
    int countAnd = 0, countX = 0, countY = 0;
    for (int i = 1; i <= persons; i++) {
        if (i % x != 0 && i % y != 0) {
            // 两个国家都可以去的员工
            countAnd++;
        } else if (i % x != 0) {
            // 只能去X国家的员工
            countX++;
        } else if (i % y != 0) {
            // 只能去Y国家的员工
            countY++;
        }
    }
    // X国家还需要多少人
    int needX = (cntX - countX) > 0 ? (cntX - countX) : 0;
    // Y国家还需要多少人
    int needY = (cntY - countY) > 0 ? (cntY - countY) : 0;

    // 两个国家都可以去的人超过X和Y两个国家所需要人之和则表示可以分配成功
    return countAnd - (needX + needY) >= 0;
}

int main() {
    scanf("%d %d %d %d", &x, &y, &cntX, &cntY);

    // 最少的人数就是每个人都去
    int min = cntX + cntY;
    // 最多的就是假设两个国家都是2，则2个只能去一个，所以都加一倍人
    int max = cntX * 2 + cntY * 2;

    while (min < max) {
        int half = (min + max) / 2;
        if (handle(half)) {
            max = half;
        } else {
            min = half + 1;
        }
    }

    printf("%d\n", min);

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static int x;
    public static int y;
    public static int cntx;
    public static int cnty;

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

        String[] inputs = sc.nextLine().split(" ");
        x = Integer.parseInt(inputs[0]);
        y = Integer.parseInt(inputs[1]);
        cntx = Integer.parseInt(inputs[2]);
        cnty = Integer.parseInt(inputs[3]);

        int result = getResult();
        System.out.println(result);
    }

    public static boolean check(int k) {
        int A = k / x; // 1~k范围内x倍数的数量
        int B = k / y; // 1~k范围内y倍数的数量
        int C = k / (x * y); // 1~k范围内x*y倍数的数量

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

    public static int getResult() {
        int low = cntx + cnty;
        // int high = Integer.MAX_VALUE; // 使用此上限，实际通过率55%
        int high = 1000000000; // 使用此上限，实际通过率可以100%

        while (low <= high) {
            int mid = (low + high) / 2;

            if (check(mid)) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }
}