2023-11-07|閱讀時間 ‧ 約 6 分鐘

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

raw-image

這題的題目在這裡:

題目敘述

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

題目會給定兩個陣列:

一個是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(n) time_of_arrival陣列,儲存怪獸抵達城市的秒數,也是抵達城市的先後順序。


關鍵知識點

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

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


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


Reference:

[1] Eliminate Maximum Number of Monsters - LeetCode

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.