class Solution {
public:
int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
}
};
6295. 最小化两个数组中的最大值
给你两个数组 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 <= 1051 <= uniqueCnt1, uniqueCnt2 < 1092 <= uniqueCnt1 + uniqueCnt2 <= 109原站题解
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-25 12:04:37
class Solution:
def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
res1 = (uniqueCnt1 - 1) * divisor1 // (divisor1 - 1) + 1
res2 = (uniqueCnt2 - 1) * divisor2 // (divisor2 - 1) + 1
LCM = lcm(divisor1, divisor2)
res3 = LCM * (uniqueCnt1 + uniqueCnt2 - 1) // (LCM - 1) + 1
return max(res1, res2, res3)
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-12-25 12:03:50
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
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2022-12-25 12:03:33
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)