1921. 消灭怪物的最大数量

原题地址

解法一

排序+贪心即可。思想为先计算出每一个怪兽到达城市的时间，然后排序，有小到大进行消灭，此时的下标可视作时间。当怪兽到达城市的时间超过或等于当前时间时，即已经到达了城市，游戏失败，下标即为消灭了多少个怪兽。O(nlogn) 时间复杂度主要在排序上。

    int eliminateMaximum(vector<int> &dist, vector<int> &speed) {int length = dist.size();vector<int> times(length);for (int i = 0; i < length; i++) {times[i] = (dist[i] - 1) / speed[i] + 1;}sort(times.begin(), times.end());for (int i = 0; i < length; i++) {if (times[i] <= i)return i;}return length;}

解法二

排序还是过于粗暴，不优雅。进一步思考优化，首先如果怪物到达的时间比怪物总数大，可以忽略，因为会尽可能先消灭到达时间快的怪物，而在怪物总数的时间时已经可以把所有怪物消灭了。相较于排序，这个解法不排序，将怪物到达的时间计数，然后从最小的开始进行怪物消灭。这时的下标不代表时间了，需要额外使用变量记录当前时间。

    int eliminateMaximum(vector<int> &dist, vector<int> &speed) {int length = dist.size();vector<int> times(length,0);for (int i = 0; i < length; i++) {int time = (dist[i] - 1) / speed[i] + 1;if (time >= length) continue;times[time]++;}int time = 0;for (int i = 0; i < length; i++) {if(!times[i]) continue;if(time+times[i]>i) return i;time += times[i];}return length;}