Question

2513. 最小化两个数组中的最大值

English Version

题目描述

给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：

• arr1 包含 uniqueCnt1 个 互不相同 的正整数，每个整数都 不能 被 divisor1 整除 。
• arr2 包含 uniqueCnt2 个 互不相同 的正整数，每个整数都 不能 被 divisor2 整除 。
• arr1 和 arr2 中的元素 互不相同 。

给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。

 

示例 1：

输入：divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
输出：4
解释：
我们可以把前 4 个自然数划分到 arr1 和 arr2 中。
arr1 = [1] 和 arr2 = [2,3,4] 。
可以看出两个数组都满足条件。
最大值是 4 ，所以返回 4 。

示例 2：

输入：divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
输出：3
解释：
arr1 = [1,2] 和 arr2 = [3] 满足所有条件。
最大值是 3 ，所以返回 3 。

示例 3：

输入：divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
输出：15
解释：
最终数组为 arr1 = [1,3,5,7,9,11,13,15] 和 arr2 = [2,6] 。
上述方案是满足所有条件的最优解。

 

提示：

• 2 <= divisor1, divisor2 <= 105
• 1 <= uniqueCnt1, uniqueCnt2 < 109
• 2 <= uniqueCnt1 + uniqueCnt2 <= 109

解法

方法一

class Solution:
  def minimizeSet(
    self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int
  ) -> int:
    def f(x):
      cnt1 = x // divisor1 * (divisor1 - 1) + x % divisor1
      cnt2 = x // divisor2 * (divisor2 - 1) + x % divisor2
      cnt = x // divisor * (divisor - 1) + x % divisor
      return (
        cnt1 >= uniqueCnt1
        and cnt2 >= uniqueCnt2
        and cnt >= uniqueCnt1 + uniqueCnt2
      )

    divisor = lcm(divisor1, divisor2)
    return bisect_left(range(10**10), True, key=f)

class Solution {
  public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    long divisor = lcm(divisor1, divisor2);
    long left = 1, right = 10000000000L;
    while (left < right) {
      long mid = (left + right) >> 1;
      long cnt1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;
      long cnt2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;
      long cnt = mid / divisor * (divisor - 1) + mid % divisor;
      if (cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && cnt >= uniqueCnt1 + uniqueCnt2) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return (int) left;
  }

  private long lcm(int a, int b) {
    return (long) a * b / gcd(a, b);
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

class Solution {
public:
  int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    long left = 1, right = 1e10;
    long divisor = lcm((long) divisor1, (long) divisor2);
    while (left < right) {
      long mid = (left + right) >> 1;
      long cnt1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;
      long cnt2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;
      long cnt = mid / divisor * (divisor - 1) + mid % divisor;
      if (cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && cnt >= uniqueCnt1 + uniqueCnt2) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
};

func minimizeSet(divisor1 int, divisor2 int, uniqueCnt1 int, uniqueCnt2 int) int {
  divisor := lcm(divisor1, divisor2)
  left, right := 1, 10000000000
  for left < right {
    mid := (left + right) >> 1
    cnt1 := mid/divisor1*(divisor1-1) + mid%divisor1
    cnt2 := mid/divisor2*(divisor2-1) + mid%divisor2
    cnt := mid/divisor*(divisor-1) + mid%divisor
    if cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && cnt >= uniqueCnt1+uniqueCnt2 {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return left
}

func lcm(a, b int) int {
  return a * b / gcd(a, b)
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  }
  return gcd(b, a%b)
}