2126. 摧毁小行星 - 力扣（LeetCode）
2126. 摧毁小行星 - 给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。 你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被 摧毁 ，并且行星会 获得 这颗小行星的质量。否则，行星将被摧毁。 如果所有小行星 都 能被摧毁，请返回 true ，否则返回 false 。 示例 1： 输入：mass =...
思路
行星撞碎小行星时会累加质量，我们可以任意排列小行星的顺序。
很明显的贪心题。对小行星进行升序排序后，质量从小到大和行星相撞，让行星不断累加质量。
如果遇到某颗小行星比行星累计质量还大，那后面的小行星必然都会把这颗行星撞碎 
。
代码
class Solution {
public:
bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
// 先按质量对小行星排序
sort(asteroids.begin(),asteroids.end());
// 排序后其实可以从小到大撞小行星
// 直至哪个小行星质量大于行星累计的质量
long long acc=mass;
for(int a:asteroids){
if(acc<a){
return false;
}
acc+=a;
}
return true;
}
};
2 个帖子 - 2 位参与者
来源: LinuxDo 最新话题查看原文