LeetCode 筆記 - 1921. Eliminate Maximum Number of Monsters

Posted on

題目在此 1921. Eliminate Maximum Number of Monsters

給訂兩個數列 dist 跟 speed，分別代表怪物的距離跟速度，每個回合可以前進 speed 個單位，在此同時我們可以選擇一個怪物攻擊，如果怪物的距離小於等於 0，堡壘則會被消滅。

請問最多可以消滅幾個怪物？

解題思維

這題的解法其實很簡單，就是先計算每個怪物到達堡壘的回合，接著排序，最後依序檢查回合數是否大於怪物抵達城市的回合數。image 106

如此一來，就知道每個怪物是否可以在抵達城市前消滅掉。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:

        if (size := len(dist)) == 1:
            return 1
        
        reach_rounds = [0] * size

        for i in range(size):
            reach_rounds[i] = dist[i] / speed[i]

        reach_rounds.sort()

        for i, r in enumerate(reach_rounds):
            if i >= r:
                return i

        return size
image 106

也許你也會想看看