消灭怪物的最大数量【力扣1921】-Toy模板网

这篇具有很好参考价值的文章主要介绍了消灭怪物的最大数量【力扣1921】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目分析

需要满足的条件：

只能在每分钟的开始使用武器
武器能杀死距离城市最近的怪兽
怪兽到达城市就会输掉游戏

游戏最优策略：我们可以在每分钟的开始都使用一次武器，用来杀死距离城市最近的怪兽。这样可以在力所能及的范围内，杀死最多的怪兽。

二、测试用例分析

消灭怪物的最大数量【力扣1921】,LeetCode练习题,leetcode,算法

示例1中打怪兽的策略可以打死 3只怪兽，其实也可以换成这样的打法：

第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X，2，3]，你消灭了第二个怪物。
第 2分钟开始时，怪物的距离是 [X，X，2]，你消灭了第三个怪物。
所有三个怪物都可以被消灭。

注意：我认为示例1中的方法不是“最优”策略。另外大家不要被这个示例误解，看第二步的时候，竟然没有消灭任何怪物，会误认为只有怪物和城市距离为1才能打死怪物；或者误认为只有在第i分钟内才能到达的怪物，才可以在i分钟时消灭。

三、解题策略

我们可以计算，每一个怪物最晚被消灭的时间，然后对时间进行排序。可以晚点消灭的怪物就会被排到后面。

例如dist=4，speed=2：

第 0 分钟开始时，怪物的距离是4，可以暂时不消灭
第 1 分钟开始时，怪物的距离是2，如果这时候不消灭的话，第2分钟开始时，怪物就到达城市，游戏失败了。
因此最晚消灭时间time=dist/speed-1=1；

例如dist=5，speed=2；

第 0 分钟开始时，怪物的距离是5，可以暂时不消灭
第 1 分钟开始时，怪物的距离是3，可以暂时不消灭
第 2 分钟开始时，怪物的距离是1，如果这时候不消灭的话，第3分钟开始时，怪物就到达城市，游戏失败了。
因此最晚消灭时间time=dist/speed=2；

总结：文章来源地址https://www.toymoban.com/news/detail-692075.html

若dist%speed==0：time=dist/speed-1；
否则：time=dist/speed；

四、示例代码

class Solution {
public:
    static bool cmp(int a,int b){
        return a<b;
    }
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        vector<int> time;
        for(int i=0;i<dist.size();i++){
            if(dist[i]%speed[i]==0){
                time.push_back(dist[i]/speed[i]-1);
            }else{
                time.push_back(dist[i]/speed[i]);
            }
        }
        sort(time.begin(),time.end(),cmp);
        int sum=0;
        for(int i=0;i<time.size();i++){
            if(i<=time[i]){
                sum++;
            }else{
                break;
            }
        }
        return sum;
    }
};

到了这里，关于消灭怪物的最大数量【力扣1921】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！