1921. 消灭怪物的最大数量

原题地址

解法一

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

    int eliminateMaximum(vector &dist, vector &speed) {
        int length = dist.size();
        vector 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12

解法二

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

    int eliminateMaximum(vector &dist, vector &speed) {
        int length = dist.size();
        vector 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16