LintCode 1683: Kill Monster (list删除重要题)

Kill Monster There are n monsters and an Altman. Both Altman and Monster have five attribute values. When Altman’s five attributes are greater than or equal to the five attributes of a monster, Altman can kill the monster. When Altman kills a monster, the five properties of the monster are added to Altman. How many monsters can Altman kill at most?

Example Example 1:

Input: n = 2, v = [[1,1,1,1,1],[1,1,1,1,1],[2,2,2,2,2]] Output: 2 Explanation: Altman kills monster v[1] at first, and his attribute changes to [2,2,2,2,2]. Then Altman can kill monster v[2] Example 2:

Input: 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]] Output: 0 Explanation: Altman can not kill any monster. Notice v[0][0]-v[0][4] means the 5 values of ALtman. v[1]-v[n] means n monsters’ 5 value5。

解法1：用list，因为删除比较快。 这里关键是遍历list的时候，因为删除了iter，会导致iter的迭代出现错误。 下面这个帖子讲了几种办法解决这个问题： https://www.cnblogs.com/dabaopku/p/3912662.html 办法1是用 monsterList.erase(iter++); 这样，删掉iter的同时，iter已经递增了。 注意，不能用

monsterList.erase(iter); iter++;

不知道为什么。 办法2是删掉的同时返回下一个iter，如

iter = a.erase(iter);

代码如下：

class Solution { public: /** * @param n: * @param v: * @return: nothing */ int killMonster(int n, vector<vector<int>> &v) { int result = 0; list<vector<int>> monsterList; for (int i = 1; i < v.size(); ++i) { monsterList.push_back(v[i]); } bool okTokill = true; while(okTokill) { okTokill = false; auto iter = monsterList.begin(); while (iter != monsterList.end()) { if (canKill(v[0], *iter)) { add(v[0], *iter); monsterList.erase(iter++); // iter++; //错误 okTokill = true; result++; } else { iter++; } } } return result; } private: bool canKill(vector<int> &altman, vector<int> &monster) { for (int i = 0; i < 5; ++i) { if (altman[i] < monster[i]) return false; } return true; } void add(vector<int> &altman, vector<int> &monster) { for (int i = 0; i < 5; ++i) { altman[i] += monster[i]; } } };

解法2：我也在考虑是否可以用最小堆来实现，堆的元素的比较函数可以是monster与altman的vector的各个元素之差距的最大值。下次再做。