LintCode 1683. 杀怪兽（队列）

1. 题目

有 n 只怪兽和一个奥特曼，奥特曼和怪兽都有5个属性值。 当且仅当奥特曼的5个属性值都不小于怪兽时，奥特曼可以杀死怪兽。 当一个怪兽被杀掉时，这个怪兽的5个属性会增加到奥特曼身上。 请问奥特曼最多可以杀死多少怪兽?

代码语言：javascript复制

样例 1:
输入: n = 2, v = [[1,1,1,1,1],[1,1,1,1,1],[2,2,2,2,2]]
输出: 2
解释: 奥特曼先杀死了怪兽 v[1], 然后他的属性值变成了 [2,2,2,2,2]. 之后奥特曼可以杀死怪兽 v[2].

样例 2:
输入: n = 5, v = [[3,9,2,1,5],[0,9,6,5,9],[6,1,8,6,3],[3,7,0,4,4],[9,9,0,6,5],[5,6,5,6,7]]
输出: 0
解释: 奥特曼无法杀死任何一个怪物.

注意事项
v[0][0]-v[0][4] 代表奥特曼的5个属性 。v[1]-v[n] 代表 n 个怪兽的5个属性 。

2. 解题

• 想着用优先队列，但是不会写，比较函数，有大佬看见，请赐教！
• 本题使用普通队列，蛮力法，依次扫描队列，最坏 O(n2) 时间复杂度

代码语言：javascript复制

class Solution {
public:
    int killMonster(int n, vector<vector<int>> &v) {
        vector<int> ot = v[0];//奥特曼
        queue<vector<int>> q;
        int count = 0, i;
        for(i = 1; i < v.size();   i)
            q.push(v[i]);//怪兽队列
        vector<int> tp;
        bool eat = true;
        while(eat)
        {
            eat = false;
            for(i = 0; i < q.size();   i)
            {
                tp = q.front();
                if(ot[0]>=tp[0]&&ot[1]>=tp[1]&&ot[2]>=tp[2]&&ot[3]>=tp[3]&&ot[4]>=tp[4])
                {
                    count  ;
                    eat = true;
                    q.pop();//吃了，删掉怪兽
                    ot[0]  = tp[0];//属性加上
                    ot[1]  = tp[1];
                    ot[2]  = tp[2];
                    ot[3]  = tp[3];
                    ot[4]  = tp[4];
                    break;//重新扫描队列
                }
                else
                {
                    q.push(tp);//回到队尾
                    q.pop();
                }
            }
            if(eat == false)//一轮下来没吃着
                break;//打败不了任何一个，退出
        }
        return count;
    }
};

100% 数据通过测试 总耗时 50 ms 您的提交打败了 63.72% 的提交!

队列

0 人点赞