遊戲模擬題 消滅最大數量的怪獸 Eliminate Max Num of Monsters_Leetcode#1921

這題的題目在這裡:

題目敘述

這題的場景是防禦城市，免於怪獸的入侵。

題目會給定兩個陣列：

一個是dist，代表怪獸和城市之間的距離。

一個是speed，代表怪獸每分鐘前進的距離，也就是怪獸的速度。

我們有一把一開始已經充滿電的電動槍，一槍可以擊殺一隻怪獸，擊發後需要耗費一分鐘的冷卻時間讓電動槍再次充滿電。

當怪獸抵達城市的時候，我們就算輸了。

題目要求我們計算最多可以消滅幾隻怪獸？

測試範例

Example 1:

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.

Example 2:

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.

Example 3:

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.

約束條件

Constraints:

• n == dist.length == speed.length
• 1 <= n <= 10^5
• 1 <= dist[i], speed[i] <= 10^5

演算法

題目已經給我們怪獸的距離，和怪獸的速度。我們可以接著計算出怪獸抵達城市的秒數。

然後，把計算出來的秒數，也就是怪獸抵達城市的先後次序由小到大排序好。

這一步驟用到了排序的觀念。

下一步，為了最大化怪獸擊殺數量，也就是最大化我方存活時間，就是依照怪獸威脅的輕重緩急，也就是怪獸抵達城市的先後次序，我們就按照這個順序去消滅怪獸。

這一步驟用到了Greedy 貪心的觀念，局部最優解導出全局最優解。

最後，當遊戲結束(怪獸已經抵達城市，或者我方率先消滅所有怪獸)時，當下的擊殺數量就是怪獸擊殺數量的最大值。

程式碼

class Solution:
　def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
　　
　　n = len(dist)

　　# Time of arrival = distance / speed
　　time_of_arrival = [ d/s for d, s in zip(dist, speed) ]

　　# Keep time of arrival sorted in ascending order
　　# And we will shoot monster with this order
　　time_of_arrival.sort()

　　# Simulate the shooting process
　　for i_th_monster in range(n):

　　　# one shot per minute
　　　shooting_time = i_th_monster
　　　
　　　if time_of_arrival[i_th_monster] <= shooting_time:
　　　　# oops, monster already get into city.
　　　　return i_th_monster

　　# It's safe now, We can emiminate all monsters!
　　# : )
　　return n

複雜度分析

時間複雜度:

O( n log n ) 耗費在怪獸秒數(也是怪獸抵達城市的先後次序)的排序上。

空間複雜度:

O(ｎ)　time_of_arrival陣列，儲存怪獸抵達城市的秒數，也是抵達城市的先後順序。

關鍵知識點

為了最大化怪獸擊殺數量，也就是最大化我方存活時間，就是依照怪獸威脅的輕重緩急，也就是怪獸抵達城市的先後次序，我們就按照這個順序去消滅怪獸。

這一步驟用到了Greedy 貪心的觀念，局部最優解導出全局最優解。

最後，當遊戲結束(怪獸已經抵達城市，或者我方率先消滅所有怪獸)時，當下的擊殺數量就是怪獸擊殺數量的最大值。

Reference:

[1] Eliminate Maximum Number of Monsters - LeetCode