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

给你两个数组 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

视频讲解已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

一看到「最大值的最小值」就想到二分答案。

下文把 divisor}_1 和 divisor}_2 简写成 d_1 和 d_2，记 LCM 为 d_1 和 d_2 的最小公倍数。

由于：

能被 d_2 整除但不能被 d_1 整除的数，能在 arr}_1 中且不能在 arr}_2 中；
能被 d_1 整除但不能被 d_2 整除的数，能在 arr}_2 中且不能在 arr}_1 中；
既不能被 d_1 整除也不能被 d_2 整除的数，可以在 arr}_1 和 arr}_2 中。

因此二分答案 x，则：

有 \left\lfloor\dfrac{x}{d_2}\right\rfloor - \left\lfloor\dfrac{x}{\textit{LCM} }\right\rfloor 个数是 arr}_1 独享的；
有 \left\lfloor\dfrac{x}{d_1}\right\rfloor - \left\lfloor\dfrac{x}{\textit{LCM} }\right\rfloor 个数是 arr}_2 独享的；
有 x - \left\lfloor\dfrac{x}{d_1}\right\rfloor - \left\lfloor\dfrac{x}{d_2}\right\rfloor + \left\lfloor\dfrac{x}{\textit{LCM} }\right\rfloor 个数（根据容斥原理）是 arr}_1 和 arr}_2 共享的。

去掉独享的，剩余的数字只能在共享中选择，因此

x - \left\lfloor\dfrac{x}{d_1}\right\rfloor - \left\lfloor\dfrac{x}{d_2}\right\rfloor + \left\lfloor\dfrac{x}{\textit{LCM} }\right\rfloor \ge \max(\textit{uniqueCnt}_1 - \left\lfloor\dfrac{x}{d_2}\right\rfloor + \left\lfloor\dfrac{x}{\textit{LCM} }\right\rfloor, 0) + \max(\textit{uniqueCnt}_2 - \left\lfloor\dfrac{x}{d_1}\right\rfloor + \left\lfloor\dfrac{x}{\textit{LCM} }\right\rfloor, 0)

为二分判定条件。

代码实现时，二分上界可以取 (\textit{uniqueCnt}_1 + \textit{uniqueCnt}_2)\cdot 2-1，因为最坏情况下 d_1=d_2=2，只能取奇数。

有关二分的写法，可以看我的【基础算法精讲 04】这期视频。

[sol1-Python3]class Solution:
    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
        lcm = math.lcm(d1, d2)
        def check(x: int) -> bool:
            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)
            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)
            common = x - x // d1 - x // d2 + x // lcm
            return common >= left1 + left2
        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)

[sol1-Go]func minimizeSet(d1, d2, uniqueCnt1, uniqueCnt2 int) int {
	lcm := d1 / gcd(d1, d2) * d2
	return sort.Search((uniqueCnt1+uniqueCnt2)*2-1, func(x int) bool {
		left1 := max(uniqueCnt1-x/d2+x/lcm, 0)
		left2 := max(uniqueCnt2-x/d1+x/lcm, 0)
		common := x - x/d1 - x/d2 + x/lcm
		return common >= left1+left2
	})
}

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

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

复杂度分析

时间复杂度：O(\log(\textit{divisor}_1+\textit{divisor}_2) + \log(\textit{uniqueCnt}_1+\textit{uniqueCnt}_2))。
空间复杂度：O(1)，仅用到若干变量。

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

复杂度分析

相似题目