Leetcode 2513. Minimize the Maximum of Two Arrays

[Woodyiiiiiii]

这道题也是经典的二分法。

难点在check函数上，如何计算不同的数。

这时候要用到数学了，用集合相交的思想，中间重叠的部分是能被公倍数整除的个数。

计算uniqueCnt1 + uniqueCnt2 <= mid - mid / lcm是检验divisor1=divisor2的情况。

class Solution {
    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        long lo = 2, hi = (int) (2 * 1e9);
        long lcm = (long) divisor1 * divisor2 / gcd(divisor1, divisor2);
        while (lo < hi) {
            long mid = (lo + hi) >> 1;
            if (uniqueCnt1 <= mid - mid / divisor1 && uniqueCnt2 <= mid - mid / divisor2 && uniqueCnt1 + uniqueCnt2 <= mid - mid / lcm) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return (int) lo;
    }

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

---

• 2513. Minimize the Maximum of Two Arrays
• 讲解
• https://leetcode.com/problems/minimize-the-maximum-of-two-arrays/solutions/2947018/beginer-friendly/