【值域二分+找规律】力扣3200-三角形的最大高度

摘要: 值域二分+找规律

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文看一个简单题，算法的框架是值域二分，二分的判定阶段不涉及算法，但是需要找规律，这里需要条理比较清晰，不然容易卡柱。

题目

• 3200. 三角形的最大高度

给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。

每一行的球必须是 相同 颜色，且相邻行的颜色必须 不同。

返回可以实现的三角形的 最大 高度。

提示：

1 <= red, blue <= 100

示例 1：
输入： red = 2, blue = 4
输出： 3
解释：
上图显示了唯一可能的排列方式。

示例 2：
输入： red = 2, blue = 1
输出： 2
解释：
上图显示了唯一可能的排列方式。

示例 3：
输入： red = 1, blue = 1
输出： 1

示例 4：
输入： red = 10, blue = 1
输出： 2
解释：
上图显示了唯一可能的排列方式。

题解

算法: 值域二分+找规律

定义 $f(n)$ 为高为 $n$ 的三角形有多少个球，可以非常直观地做出猜想 $f(n) = \frac{1}{2}n(n+1)$，其中有一部分是奇数行的球、一部分是偶数行的球，分别记为 $g_{1}(n)$、$g_{2}(n)$，有 $f(n) = g_{1}(n) + g_{2}(n)$。

对于输入 $r$ 和 $b$，在取值范围 $[l, r]$ 上二分三角形的高度 $n$，求出 $g_{1}(n)$ 和 $g_{2}(n)$。如果 $\max(r, b) \geq \max(g_{1}(n), g_{2}(n))$ 且 $\min(r, b) \geq \min(g_{1}(n), g_{2}(n))$，则 $(r, b)$ 可以至少可以满足高度为 $n$ 的三角形，答案可能更大，取 $l = n$ 进行下一轮；否则 $(a, b)$ 无法满足高度为 $n$ 的三角形，答案只会更小，因此置 $r = n - 1$ 进行下一轮即可。

下面的问题就是对于高度 $n$ 如何给出 $g_{1}(n)$ 和 $g_{2}(n)$。

当 $n$ 为偶数时，奇数行为 $1, 3, 5, \cdots, n-1$，共 $\frac{n}{2}$ 行，因此 $g_{1}(n) = \frac{1}{2}(1 + (n - 1))\frac{n}{2} = \frac{n^{2}}{4}$；偶数行为 $2, 4, 6, \cdots, n$，共 $\frac{n}{2}$ 行，因此 $g_{2}(n) = \frac{1}{2}(2 + n)\frac{n}{2} = \frac{n(n+2)}{2}$。

当 $n$ 为奇数时，奇数行为 $1, 3, 5, \cdots, n$，共 $\frac{n+1}{2}$ 行，因此 $g_{1}(n) = \frac{1}{2}(1 + n)\frac{n+1}{2}$；偶数行为 $2, 4, 6, \cdots, n - 1$，共 $\frac{n-1}{2}$ 行，因此 $g_{2}(n) = \frac{1}{2}(2 + (n-1))\frac{n-1}{2}$。

代码 (Python)

def func_g1(n):
    if n % 2 == 0:
        return n * n // 4
    else:
        return (n + 1) * (n + 1) // 4

def func_g2(n):
    if n % 2 == 0:
        return n * (n + 2) // 4
    else:
        return (n - 1) * (n + 1) // 4

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        left = 0
        right = int(1e10)
        while left < right:
            mid = (left + right + 1) // 2
            g1 = func_g1(mid)
            g2 = func_g2(mid)
            if min(red, blue) >= min(g1, g2) and max(red, blue) >= max(g1, g2):
                left = mid
            else:
                right = mid - 1
        return left

---