leetcode 2126. 摧毁小行星 中等

给你一个整数mass，它表示一颗行星的初始质量。再给你一个整数数组asteroids，其中asteroids[i]是第i颗小行星的质量。

你可以按任意顺序重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量大于等于小行星的质量，那么小行星被摧毁，并且行星会获得这颗小行星的质量。否则，行星将被摧毁。

如果所有小行星都能被摧毁，请返回true，否则返回false。

示例 1：

输入：mass = 10, asteroids = [3,9,19,5,21]输出：true解释：一种安排小行星的方式为 [9,19,5,3,21] ： - 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19 - 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38 - 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43 - 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46 - 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67 所有小行星都被摧毁。

示例 2：

输入：mass = 5, asteroids = [4,9,23,4]输出：false解释：行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。 行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。 它比 23 小，所以无法摧毁最后一颗小行星。

提示：

• 1 <= mass <= 10^5
• 1 <= asteroids.length <= 10^5
• 1 <= asteroids[i] <= 10^5

分析：先将小行星按照质量从小到大排序，记录最大的小行星质量。接着依次碰撞并更新行星质量，如果某个小行星的质量大于了当前的行星质量，说明这颗小行星无法被摧毁，返回 false；如果行星质量大于小行星的最大质量，说明所有小行星都可以被摧毁，返回 true。

class Solution { public: bool asteroidsDestroyed(int mass, vector<int>& asteroids) { int n=asteroids.size(),maxn=-1; sort(asteroids.begin(),asteroids.end());maxn=asteroids[n-1]; for(int i=0;i<n;++i) { if(mass>=asteroids[i])mass+=asteroids[i]; else return false; if(mass>=maxn)return true; } return true; } };