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

https://leetcode.cn/problems/minimize-the-maximum-of-two-arrays/

这题初看起来不怎么难，但是可让我想了好长时间，把这个思路理顺了之后就还好。可见清晰通畅的思路是多么地重要，即使知道框架但是没有清晰的思路，写起来也会是相当纠结的。

这题总体的框架就是二分，二分的上限是 `2*(uniqueCount1 + uniqueCount2)` 因为divisor最小就是2，如果两个divisor都是2的话，那么只需要取所有的奇数就行。

主体就是怎么写这个二分，假设最大的数是k：

那么可以同时被group1/2使用的数量是 `a = k - k / divisor1 - k / divisor2 + k / lcm`
只能被group1使用的数量则是 `b = (k - k / divisor1) - a`
只能被group2使用的数量则是 `c = (k - k / divisor1) - a`
分配的时候我们优先满足group1, 并且优先使用 "只能被group1使用的数"，如果不满足条件就返回false: `(b + a) < uniqueCount1`
剩余的数量在和 "只能被group2使用的数" 累加，如果不满足条件就返回false。
注意这里剩余的数量中，我们只能选择 "可以同时被group1/2使用的数": `min(a, (b+a) - uniqueCount1) + c < uniqueCount2`

class Solution:
    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
        def GCD(a, b):
            while b != 0:
                a, b = b, a % b
            return a

        def LCM(a, b):
            return a * b // GCD(a, b)

        def test(k):
            lcm = LCM(divisor1, divisor2)
            # be used to g1 and g2 both
            a = k - k // divisor1 - k // divisor2 + k // lcm
            # only to g1
            b = (k - k // divisor1) - a
            # only to g2
            c = (k - k // divisor2) - a

            if (b + a) < uniqueCnt1: return False
            r = min(a, (b + a) - uniqueCnt1)
            if (r + c) < uniqueCnt2: return False
            return True

        s, e = 1, (uniqueCnt1 + uniqueCnt2) * 2
        while s <= e:
            m = (s + e) // 2
            if test(m):
                e = m - 1
            else:
                s = m + 1
        return s