前往
大廳
主題

LeetCode - 1921. Eliminate Maximum Number of Monsters 解題心得

Not In My Back Yard | 2021-10-31 00:00:07 | 巴幣 10 | 人氣 221

題目連結:


題目意譯:
你正在遊玩一個電子遊戲其中你正保衛著你的城市免於 n 隻怪獸。你被給定一個索引值從 0 開始的長度 n 之整數陣列 dist,其中 dist[i] 為第 i 隻怪獸距離城市的初始距離。

怪獸以穩定速度走向城市。每隻怪獸的速度給定於一個長度 n 的整數陣列 speed,其中 speed[i] 為第 i 隻怪獸每分鐘公尺數的速度。

怪獸開始移動於分鐘 0。你有著一個武器可以在每分鐘開頭選擇去使用,包含分鐘 0。你不得在某分鐘之中內使用該武器。該武器可以消滅任何一隻尚存活的怪獸。當有任何怪獸抵達你的城市時你就輸了。如果一隻怪獸恰好於某分鐘的開頭抵達城市,則仍算作一個失敗,且遊戲將在你能在該分鐘內使用武器前就結束了。

回傳最大你在輸掉之前可以消滅的怪獸數,或是回傳 n 如果你能在它們抵達城市之前消滅所有的怪獸。

限制:
n == dist.length == speed.length
1 ≦ n ≦ 10 ^ 5
1 ≦ dist[i] 、 speed[i] ≦ 10 ^ 5



範例測資:
範例 1:
輸入: dist = [1,3,4], speed = [1,1,1]
輸出: 3
解釋:
分鐘 0 的開頭,怪獸的距離為 [1,3,4],而你消滅了第一隻怪獸。
分鐘 1 的開頭,怪獸的距離為 [X,2,3],而你什麼都不做。
分鐘 2 的開頭,怪獸的距離為 [X,1,2],而你消滅了第二隻怪獸。
分鐘 3 的開頭,怪獸的距離為 [X,X,1],而你消滅了第三隻怪獸。
所有三隻怪獸都被消滅了。

範例 2:
輸入: dist = [1,1,2,3], speed = [1,1,1,1]
輸出: 1
解釋:
分鐘 0 的開頭,怪獸的距離為 [1,1,2,3],而你消滅了第一隻怪獸。
分鐘 1 的開頭,怪獸的距離為 [X,0,1,2],而你輸了。
你只能消滅一隻怪獸。

範例 3:
輸入: dist = [3,2,4], speed = [5,3,2]
輸出: 1
解釋:
分鐘 0 的開頭,怪獸的距離為 [3,2,4],而你消滅了第一隻怪獸。
分鐘 1 的開頭,怪獸的距離為 [X,0,2],而你輸了。
你只能消滅一隻怪獸。


解題思維:
直接將所有怪獸按照它們的抵達時間取整數之值(即 ceil(距離 ÷ 速度),其中 ceil 為上高斯函數(對於非負數即無條件進位至整數))由小排到大。然後從抵達時間小的怪獸開始消滅起。

因此一開始我們的時間位於 t = 0 秒。只要還有怪獸且 t < 當前怪獸的抵達時間,代表我們還可以消滅另一隻怪獸,因此將 t 加 1(每一秒只能使用一次武器)。

最後的 t 值即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作