你正在玩一款電子游戲，在游戲中你需要保護(hù)城市免受怪物侵襲。給你一個(gè) 下標(biāo)從 0 開(kāi)始 且長(zhǎng)度為 n 的整數(shù)數(shù)組 dist ，其中 dist[i] 是第 i 個(gè)怪物與城市的 初始距離（單位：米）。
怪物以 恒定 的速度走向城市。給你一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 speed 表示每個(gè)怪物的速度，其中 speed[i] 是第 i 個(gè)怪物的速度（單位：米/分）。
怪物從 第 0 分鐘 時(shí)開(kāi)始移動(dòng)。你有一把武器，并可以 選擇 在每一分鐘的開(kāi)始時(shí)使用，包括第 0 分鐘。但是你無(wú)法在一分鐘的中間使用武器。這種武器威力驚人，一次可以消滅任一還活著的怪物。
一旦任一怪物到達(dá)城市，你就輸?shù)袅诉@場(chǎng)游戲。如果某個(gè)怪物 恰 在某一分鐘開(kāi)始時(shí)到達(dá)城市，這會(huì)被視為 輸?shù)?游戲，在你可以使用武器之前，游戲就會(huì)結(jié)束。
返回在你輸?shù)粲螒蚯翱梢韵麥绲墓治锏?最大 數(shù)量。如果你可以在所有怪物到達(dá)城市前將它們?nèi)肯麥?，返? n 。
n == dist.length == speed.length
1 <= n <= 105
1 <= dist[i], speed[i] <= 105
例子:
輸入：dist = [1,3,4], speed = [1,1,1]
輸出：3
解釋：
第 0 分鐘開(kāi)始時(shí)，怪物的距離是 [1,3,4]，你消滅了第一個(gè)怪物。
第 1 分鐘開(kāi)始時(shí)，怪物的距離是 [X,2,3]，你沒(méi)有消滅任何怪物。
第 2 分鐘開(kāi)始時(shí)，怪物的距離是 [X,1,2]，你消滅了第二個(gè)怪物。
第 3 分鐘開(kāi)始時(shí)，怪物的距離是 [X,X,1]，你消滅了第三個(gè)怪物。
所有 3 個(gè)怪物都可以被消滅。
輸入：dist = [1,1,2,3], speed = [1,1,1,1]
輸出：1
解釋：
第 0 分鐘開(kāi)始時(shí)，怪物的距離是 [1,1,2,3]，你消滅了第一個(gè)怪物。
第 1 分鐘開(kāi)始時(shí)，怪物的距離是 [X,0,1,2]，你輸?shù)袅擞螒颉?br>
你只能消滅 1 個(gè)怪物。
輸入：dist = [3,2,4], speed = [5,3,2]
輸出：1
解釋：
第 0 分鐘開(kāi)始時(shí)，怪物的距離是 [3,2,4]，你消滅了第一個(gè)怪物。
第 1 分鐘開(kāi)始時(shí)，怪物的距離是 [X,0,2]，你輸?shù)袅擞螒颉?br>
你只能消滅 1 個(gè)怪物。
解題思路:
貪心 + 排序
先補(bǔ)充個(gè)知識(shí)點(diǎn):
貪心算法:（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，算法得到的是在某種意義上的局部最優(yōu)解。
這道題我們按照題意硬翻譯的話不太好處理, 那么我們可以轉(zhuǎn)換下思路
首先因?yàn)橐恢泵恐还肢F初始距離dist[i], 初始速度speed[i], 那么消滅每個(gè)怪獸到達(dá)城市最小時(shí)間為: dist[i] / speed[i]
例如: 初始距離2, 速度1, 我們需要 2 / 1 = 2分鐘時(shí)候消費(fèi)怪獸, 對(duì)嗎? 這么想就錯(cuò)了!!! 2分鐘再開(kāi)火, 怪獸都騎到臉上了, 直接GG。要在1分鐘時(shí)候?qū)⑵湎麥?/p>
實(shí)際上最小消滅時(shí)間應(yīng)該為: (dist[i] - 1) / speed[i]
那么我們依次計(jì)算出每個(gè)怪獸應(yīng)該消滅最小時(shí)間time數(shù)組, 做一次正序排列
再依次循環(huán)time數(shù)組, 判斷time[i] - i是否小于0
例如:
時(shí)間數(shù)組 time 為 [0, 1, 2], 那么我們
- 第0分鐘消滅到達(dá)時(shí)間為0的怪獸
- 第1分鐘消滅到達(dá)時(shí)間為1的怪獸
- 第2分鐘消滅到達(dá)時(shí)間為2的怪獸
故滿足
dist[i]: [1, 1, 3], speed[1, 1, 1]
時(shí)間數(shù)組 time 為 [0, 0, 2], 那么我們
- 第0分鐘消滅到達(dá)時(shí)間為0的怪獸
但是在1分鐘實(shí)際上有2只到達(dá), 我們同一時(shí)間點(diǎn)只能消滅1只, 故不滿足
代碼
未翻譯版
func eliminateMaximum(_ dist: [Int], _ speed: [Int]) -> Int {
var res = 0, time = Array(repeating: 0, count: dist.count)
for i in 0..<dist.count {
time[i] = (dist[i] - 1) / speed[i]
}
time.sort()
for i in 0..<time.count {
if time[i] - i < 0 {
break;
}
res += 1
}
return res;
}
翻譯版
func eliminateMaximum(_ dist: [Int], _ speed: [Int]) -> Int {
// 定義結(jié)果res, 空數(shù)組time, 用來(lái)存放最小消滅時(shí)間
var res = 0, time = Array(repeating: 0, count: dist.count)
// 遍歷, 存放最小消滅時(shí)間的空數(shù)組
for i in 0..<dist.count {
// 空數(shù)組依次插入最小消滅時(shí)間
time[i] = (dist[i] - 1) / speed[i]
}
// 時(shí)間數(shù)組正序排列
time.sort()
// 遍歷時(shí)間數(shù)組
for i in 0..<time.count {
// 如果 當(dāng)前時(shí)間小于
if time[i] - i < 0 {
break;
}
// 滿足 消滅結(jié)果 + 1
res += 1
}
// 返回 最大消滅數(shù)量res
return res;
}
題目來(lái)源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址
