2126. Destroying Asteroids

題目 / Problem

中文 給定一個整數 mass，代表一顆行星的初始質量。再給定一個整數陣列 asteroids，其中 asteroids[i] 是第 i 顆小行星的質量。

你可以任意安排行星和小行星碰撞的順序。每次碰撞時： - 如果行星的質量大於或等於這顆小行星的質量，小行星被摧毀，行星吸收它的質量（質量相加）。 - 否則，行星自己被摧毀。

如果所有小行星都能被摧毀，回傳 true；否則回傳 false。

English You are given an integer mass, the planet's starting mass, and an array asteroids where asteroids[i] is the mass of the i-th asteroid. You may collide the planet with the asteroids in any order. On each collision, if the planet's mass is ≥ the asteroid's mass, the asteroid is destroyed and the planet gains that mass; otherwise the planet is destroyed. Return true if all asteroids can be destroyed, else false.

Constraints / 限制 - 1 <= mass <= 10^5 - 1 <= asteroids.length <= 10^5 - 1 <= asteroids[i] <= 10^5

Worked example / 範例 mass = 10, asteroids = [3,9,19,5,21] → true. 依序撞 9,19,5,3,21：質量變化 10 → 19 → 38 → 43 → 46 → 67，全部摧毀。

名詞解釋 / Glossary

• 貪心 / Greedy：在每一步都做「當下看起來最好」的選擇，並證明這些局部最優選擇能組成全域最優解。這題的最佳選擇是：每次都撞還沒撞、且質量最小的那顆小行星。
• 排序 / Sorting：把陣列依某種順序（這裡是由小到大，non-decreasing）重新排列。排序後我們就能從最小開始一顆一顆撞。
• 不變量 / Invariant：在迴圈執行過程中始終保持為真的性質。這裡的不變量是：「目前的 mass 等於初始質量加上已摧毀的所有小行星質量」。
• 溢位 / Overflow：當數值超過資料型別能表示的最大值時發生的錯誤。32 位元的 int 最大約 21 億；本題質量總和最多約 10^5 + 10^5 × 10^5 = 100 億，超過 int，所以累加要用 64 位元整數（long long）。
• 比較函式 / Comparator：傳給排序函式、告訴它「兩個元素誰應該排前面」的小函式。C 的 qsort 需要它，C++ 的 std::sort 預設由小到大就夠用。

思路

最直覺的暴力想法是：嘗試所有可能的碰撞順序，看看有沒有任何一種順序能摧毀全部小行星。但 n 顆小行星有 n!（階乘）種排列，當 n = 10^5 時這是天文數字，完全不可行。我們需要找到規律。觀察題目提示：如果行星「現在」就撞不過某顆小行星，那它撞不過的就一定是「目前最大」的那一顆嗎？反過來想更清楚——在任一時刻，行星只會因為撞到「比自己大的小行星」而被毀。為了讓行星活得最久、長得最大，我們應該先撞小的：每吃掉一顆小的，行星就變重一點，更有本錢去對付後面大的。因此最佳策略是把小行星由小到大排序，然後依序碰撞。每一步檢查「當前質量是否 ≥ 這顆小行星」；只要有一顆過不了就回傳 false，因為若連最小的剩餘小行星都撞不過，更大的更不可能。全部撞完就回傳 true。關鍵不變量是：迴圈中 mass 永遠等於初始質量加上已吸收的質量總和，所以累加要用能裝下 100 億的 64 位元整數以避免溢位。

The brute-force idea is to try every collision order and see if any of them destroys all asteroids, but there are n! orderings — utterly infeasible for n up to 10^5. The insight comes from the greedy structure: the planet only dies when it hits an asteroid heavier than itself, so to survive longest and grow biggest, we should always eat the smallest available asteroid first. Every small asteroid we absorb makes the planet heavier, giving it more power for the bigger ones later. So we sort the asteroids in non-decreasing order and collide with them one by one. At each step we check whether the current mass is ≥ the asteroid; if even the smallest remaining asteroid can't be destroyed, no larger one can either, so we return false. If we get through all of them, we return true. The invariant is that mass always equals the original mass plus everything absorbed so far — and since that sum can reach ~10 billion, we accumulate in a 64-bit integer to avoid overflow.

逐步走查 / Walkthrough

Input: mass = 10, asteroids = [3,9,19,5,21]

Step 1 — sort ascending / 由小到大排序：[3, 5, 9, 19, 21] Start with cur = 10 (use 64-bit) / 初始 cur = 10。

所有小行星都被摧毀，回傳 true。 / All asteroids destroyed → return true.

(對比 / Contrast: mass = 5, [4,9,23,4] 排序成 [4,4,9,23]，累加到 5+4+4+9 = 22，撞 23 時 22 < 23 ❌，回傳 false。)

Solution — C

// 演算法：把小行星由小到大排序，依序碰撞。/ Algorithm: sort asteroids ascending, collide in order.
// 每次都吃最小的，行星越長越重；若連最小的剩餘小行星都撞不過就失敗。
// Always eat the smallest first so the planet grows; if even that fails, return false.

// qsort 需要的比較函式：回傳負/零/正代表 a 排在 b 前/相等/後。
// Comparator for qsort: return negative/zero/positive means a goes before/equal/after b.
int cmp(const void *a, const void *b) {
    // *(const int *)a 是把 void 指標轉回 int 指標再取值 / cast void* back to int* then dereference.
    int x = *(const int *)a;
    int y = *(const int *)b;
    // 用相減可能溢位，所以用比較式回傳 -1/0/1 比較安全。
    // Subtraction could overflow, so compare and return -1/0/1 instead.
    return (x > y) - (x < y);
}

bool asteroidsDestroyed(int mass, int* asteroids, int asteroidsSize) {
    // 原地把陣列由小到大排序 / sort the array ascending in place.
    // 參數：起始位址、元素個數、每個元素的位元組大小、比較函式。
    // Args: start address, element count, size of each element, comparator.
    qsort(asteroids, asteroidsSize, sizeof(int), cmp);

    // cur 用 long long（64 位元）避免溢位，初始為行星質量。
    // cur is long long (64-bit) to avoid overflow; starts as the planet's mass.
    long long cur = mass;

    // 從最小的小行星開始一顆一顆撞 / loop through asteroids smallest first.
    for (int i = 0; i < asteroidsSize; i++) {
        // 若現在質量小於這顆小行星，行星被毀，無法全部摧毀。
        // If current mass is smaller than this asteroid, the planet dies → cannot destroy all.
        if (cur < asteroids[i]) {
            return false;
        }
        // 否則摧毀它並吸收其質量 / otherwise destroy it and absorb its mass.
        cur += asteroids[i];
    }

    // 全部撞完都沒失敗，代表可以摧毀所有小行星。
    // Got through all without failing → every asteroid can be destroyed.
    return true;
}

Solution — C++

// 演算法：小行星由小到大排序後依序碰撞，貪心地先吃最小的。
// Algorithm: sort ascending, then greedily collide smallest-first.
// 累加用 long long 防溢位；任何一顆撞不過就回傳 false。
// Accumulate in long long to avoid overflow; any failed collision → false.

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        // std::sort 預設由小到大排序 vector / std::sort orders the vector ascending by default.
        // 參數是「起點迭代器」和「終點迭代器」/ takes begin() and end() iterators.
        sort(asteroids.begin(), asteroids.end());

        // cur 用 long long 避免質量總和超過 int 範圍 / long long avoids int overflow on the running sum.
        long long cur = mass;

        // range-for：依序取出每顆小行星的質量 a / range-for iterates each asteroid's mass a.
        // 用 const int& 避免複製、且表明不修改 / const int& avoids a copy and signals no mutation.
        for (const int& a : asteroids) {
            // 若當前質量撞不過這顆（最小的剩餘）小行星，直接失敗。
            // If current mass can't beat this (smallest remaining) asteroid, fail immediately.
            if (cur < a) return false;
            // 否則吸收它的質量 / otherwise absorb its mass.
            cur += a;
        }

        // 全部成功摧毀 / all destroyed successfully.
        return true;
    }
};

複雜度 / Complexity

• Time: O(n log n) — n 是小行星數量。排序需要 O(n log n)，是主導項；之後只掃一遍陣列是 O(n)，加起來仍是 O(n log n)。 / n is the number of asteroids; sorting dominates at O(n log n), the single linear pass adds only O(n).
• Space: O(1) 額外空間（不計排序遞迴堆疊）— 我們原地排序、只用幾個變數。 / Extra space is O(1) (ignoring sort's internal stack); we sort in place and use only a couple of variables.

Pitfalls & Edge Cases

• 整數溢位 / Integer overflow：質量總和最多約 10^5 + 10^5 × 10^5 ≈ 100 億，遠超 32 位元 int（約 21 億）。若用 int 累加會溢位算出錯誤結果，所以 cur 必須是 long long。 / The running sum can reach ~10 billion, overflowing a 32-bit int; accumulate in long long.
• 比較用「≥」而非「>」/ Use ≥, not >：質量相等時小行星仍會被摧毀。程式碼用 if (cur < a) return false，等號情況 (cur == a) 不觸發失敗，正確地讓它通過。 / Equal masses still destroy the asteroid; cur < a correctly lets the equal case pass.
• 必須先排序 / Must sort first：若不排序而照原順序撞，可能先碰到大的而提早失敗，得到錯誤的 false。貪心的正確性建立在「由小到大」之上。 / Without sorting you might hit a large asteroid early and wrongly return false; greedy correctness depends on ascending order.
• qsort 比較函式別用相減 / Don't subtract in the comparator：return x - y 在極端值下也可能溢位；本解用 (x>y)-(x<y) 安全回傳順序。 / x - y can overflow; use the sign-comparison trick instead.
• 單一小行星 / Single asteroid：asteroids.length 最小為 1，迴圈自然處理，無需特例。 / The minimum length is 1; the loop handles it without special-casing.