🔗 🟢 3200. Maximum Height of a Triangle 1451

tags: Weekly Contest 404 陣列(Array) 枚舉(Enumeration) 數學(Math)

題意

給定兩個整數 redred 和 blueblue，分別表示紅色和藍色球的數量。你需要將這些球排列成一個三角形，使得第 11 行有 11 個球，第 22 行有 22 個球，第 33 行有 33 個球，以此類推。

同一行的所有球應該是 相同 的顏色，且相鄰行應該是 不同 的顏色。

返回所能達到的三角形的 最大高度。

約束條件

  • 1≤red,blue≤1001 \leq red, blue \leq 100

思路：枚舉高度 / 數學計算

方法一：枚舉高度

注意到紅色和藍色球數量最多只有 100100 個，而三角形的最高高度滿足 1+2+3+...+h=h(h+1)2≤(red+blue)1 + 2 + 3 + ... + h = \frac{h(h + 1)}{2} \leq (red + blue)，因此三角形的高度最多為 200≈14\sqrt{200} \approx 14 行。

因此我們可以枚舉三角形的高度，並檢查是否能夠構建出對應的三角形結構。並且由於三角形的高度是遞增的，因此我們可以從高度 11 開始枚舉，直到無法構建出對應的三角形結構為止。

具體來說，對於每一個高度 hh，我們需要檢查是否能夠使用給定的紅色和藍色球來構建出對應的三角形結構。定義一個函數 check(x, y)，用來計算當第一行為紅色球，且紅色球數量為 xx，藍色球數量為 yy 時，能夠達到的最大高度。

  • 如果當前行數為奇數，則使用紅色球，並檢查紅色球是否足夠。如果足夠，則減去該行所需的紅色球數量；否則，停止檢查。
  • 如果當前行數為偶數，則使用藍色球，並檢查藍色球是否足夠。如果足夠，則減去該行所需的藍色球數量；否則，停止檢查。
  • 逐行增加高度，直到不能滿足條件為止。

最後，我們需要分別考慮兩種顏色起始的情況，取其中能夠構建的更高的三角形高度作為最終結果。

複雜度分析

  • 時間複雜度：O(h)=O(n+m)\mathcal{O}(h) = \mathcal{O}(\sqrt{n + m})，其中 hh 是三角形的高度，nn 和 mm 分別是紅色和藍色球的數量。
  • 空間複雜度：O(1)\mathcal{O}(1)，只使用了常數額外空間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def check(x: int, y: int) -> int:
            cur = 1
            while x > 0 or y > 0:
                if cur & 1: # odd
                    if x >= cur:
                        x -= cur
                    else:
                        break
                else: # even
                    if y >= cur:
                        y -= cur
                    else:
                        break
                cur += 1
            return cur - 1
        return max(check(red, blue), check(blue, red))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxHeightOfTriangle(int red, int blue) {
        function<int(int, int)> check = [&](int x, int y) -> int {
            int cur = 1;
            while (x > 0 || y > 0) {
                if (cur & 1) {
                    if (x >= cur) {
                        x -= cur;
                    } else {
                        break;
                    }
                } else {
                    if (y >= cur) {
                        y -= cur;
                    } else {
                        break;
                    }
                }
                cur += 1;
            }
            return cur - 1;
        };
        return max(check(red, blue), check(blue, red));
    }
};

方法二：數學計算

注意到在方法一中的複雜度計算中，我們使用了數學公式來計算三角形的高度。類似地，我們也可以使用數學公式來直接計算出能夠組成的最大高度，而不需要逐步嘗試每一層的可能性。

同樣地，我們定義一個函數 check(x, y)，用來計算當紅色球在奇數層，藍色球在偶數層時，且紅色球數量為 xx，藍色球數量為 yy 時，能夠達到的最大高度。並透過數學公式直接計算出能夠組成的最大高度，以下是詳細的計算步驟：

  1. 計算紅色球能支撐的最大奇數層數（t1t_1）：
    • 每個奇數層需要的紅色球數量形成一個等差數列：1,3,5,...,(2×t1−1)1, 3, 5, ..., (2 \times t_1 - 1)。這個數列的總和可以表示為：

    1+3+5+...+(2×t1−1)=t12≤x1 + 3 + 5 + ... + (2 \times t_1 - 1) = t_1^2 \leq x

    • 因此，我們可以利用紅色球的總數量 xx，通過取其平方根來得到最大可能的奇數層數：

    t1=⌊x⌋t_1 = \lfloor \sqrt{x} \rfloor

  2. 計算藍色球能支撐的最大偶數層數（t2t_2）：
    • 每個偶數層需要的藍色球數量形成一個等差數列：2,4,6,...,(2×t2)2, 4, 6, ..., (2 \times t_2)。這個數列的總和可以表示為：

    S=2+4+6+...+(2×t2)=t2×(t2+1)≤yS = 2 + 4 + 6 + ... + (2 \times t_2) = t_2 \times (t_2 + 1) \leq y

    • 因此，我們可以利用藍色球的總數量 yy，通過解二次方程來得到最大可能的偶數層數：

    t22+t2≤yt_2^2 + t_2 \leq y

    • 解這個二次方程，我們可以得到：

    t2=⌊−1+1+4×y2⌋t_2 = \lfloor \frac{-1 + \sqrt{1 + 4 \times y}}{2} \rfloor

    • 如果 t1>t2t_1 > t_2，那麼可以構成 t2+1t_2 + 1 行紅色球和 t2t_2 行藍色球，因此最大高度為 2×t2+12 \times t_2 + 1。
    • 否則，可以構成 t1t_1 行紅色球和 t1t_1 行藍色球，因此最大高度為 2×t12 \times t_1。

同樣地，我們需要分別考慮兩種顏色起始的情況，取其中能夠構建的更高的三角形高度作為最終結果。

複雜度分析

  • 時間複雜度：O(1)\mathcal{O}(1)，只進行了常數次數的計算。
    • sqrt 函數的時間複雜度可以視為 O(1)\mathcal{O}(1)。
  • 空間複雜度：O(1)\mathcal{O}(1)，只使用了常數額外空間。
1
2
3
4
5
6
7
class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def check(x: int, y: int) -> int:
            t1 = int(math.sqrt(x))
            t2 = int((-1 + math.sqrt(1 + 4 * y)) / 2)
            return t2 * 2 + 1 if t1 > t2 else t1 * 2
        return max(check(red, blue), check(blue, red))
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxHeightOfTriangle(int red, int blue) {
        function<int(int, int)> check = [&](int x, int y) -> int {
            int t1 = floor(sqrt(x));
            int t2 = floor((-1 + sqrt(1 + 4 * y)) / 2);
            return t1 > t2 ? t2 << 1 | 1 : t1 << 1;
        };
        return max(check(red, blue), check(blue, red));
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), long hair, (black eyes), looking at viewer, (standing), full body, black hair, school uniform, short sleeves, pleated skirt, skirt, shirt, (green top, green shirt), black bottom, (black skirt), serafuku, socks, looking back, indoors, sailor collar, black footwear, window, white socks, hallway,

A girl in a green shirt and black pleated skirt standing, in a long school hallway, windows and doors on both sides, bright natural light coming through the windows, serene atmosphere, looking back at the camera,