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

题目链接

Leetcode.2513 最小化两个数组中的最大值 Rating ： 2302

题目描述

给你两个数组 $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<=1052 <= divisor1, divisor2 <= 10^52<=divisor1,divisor2<=105
• 1<=uniqueCnt1,uniqueCnt2<1091 <= uniqueCnt1, uniqueCnt2 < 10^91<=uniqueCnt1,uniqueCnt2<109
• 2<=uniqueCnt1+uniqueCnt2<=1092 <= uniqueCnt1 + uniqueCnt2 <= 10^92<=uniqueCnt1+uniqueCnt2<=109

解法：二分 + 容斥原理

技巧：一般题目出现 最大 最小，多半正解就是二分。

我们做出如下定义：

• 定义 $A$ 是不能被 $divisor1$整除，但是可以被 $divisor2$ 整除的数，也就是只能放在$arr1$ 中的数，即 $x/divisor2-x/lcm(divisor1,divisor2)$
• 定义 $B$ 是不能被 $divisor2$整除，但是可以被 $divisor1$ 整除的数，也就是只能放在$arr2$ 中的数，即 $x/divisor1-x/lcm(divisor1,divisor2)$
• 定义 $C$ 是既不能被 $divisor1$整除，也不能被 $divisor2$ 整除的数，也就是$arr1和arr2$ 都可以放的数，即 $x-x/divisor1-x/divisor2+x/lcm(divisor1,divisor2)$

对于 $uniqueCnt1,uniqueCnt2$ 我们先使用 $A$ 和 $B$ 的数字，等到使用结束，还需要数字的时候，再使用共享的 $C$ 中的数字。

$uniqueCnt1,uniqueCnt2$ 使用完 $A$ 和 $B$ 的数字后，各自还剩 $cnt1和cnt2$：

• cnt1=max{uniqueCnt1−A,0}cnt1 = max\\{ uniqueCnt1 - A , 0\\}cnt1=max{uniqueCnt1−A,0}
• cnt2=max{uniqueCnt2−B,0}cnt2 = max\\{ uniqueCnt2 - B , 0\\}cnt2=max{uniqueCnt2−B,0}

接下来再判断共享的 $C$ 的中数字数量是否大于 $cnt1+cnt2$，即 $C\ge cnt1+cnt2$。

左边界 $l=2$ ；右边界 $r=(uniqueCnt1+uniqueCnt2)\ast 2$。

时间复杂度： $O(logr)$

C++代码：

using LL = long long;class Solution {
public:int minimizeSet(int d1, int d2, int uniqueCnt1, int uniqueCnt2) {LL l = 2 , r = 2 * 1LL * (uniqueCnt1 + uniqueCnt2);LL lc = lcm<LL>(d1,d2);while(l < r){LL mid  = (l + r) >> 1;//能被 d2 整除，但是不能被 d1 整除的数LL a = mid / d2 - mid / lc;//能被 d1 整除，不能被 d2 整除的数LL b = mid / d1 - mid / lc;//既不能被 d1 也不能被 d2 整除的数，即共享的数LL c = mid - mid/d1 - mid/d2 + mid/lc;LL cnt1 = max(uniqueCnt1 - a,0LL) , cnt2 = max(uniqueCnt2-b,0LL);if(c >= cnt1 + cnt2) r = mid;else l = mid + 1;}return (int)l;}
};