你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ，其中 dist[i] 是第 i 个怪物与城市的 初始距离（单位：米）。
怪物以 恒定 的速度走向城市。给你一个长度为 n 的整数数组 speed 表示每个怪物的速度，其中 speed[i] 是第 i 个怪物的速度（单位：米/分）。
怪物从 第 0 分钟 时开始移动。你有一把武器，并可以 选择 在每一分钟的开始时使用，包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人，一次可以消灭任一还活着的怪物。
一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物 恰 在某一分钟开始时到达城市，这会被视为 输掉 游戏，在你可以使用武器之前，游戏就会结束。
返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回 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 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,2,3]，你没有消灭任何怪物。
第 2 分钟开始时，怪物的距离是 [X,1,2]，你消灭了第二个怪物。
第 3 分钟开始时，怪物的距离是 [X,X,1]，你消灭了第三个怪物。
所有 3 个怪物都可以被消灭。
输入：dist = [1,1,2,3], speed = [1,1,1,1]
输出：1
解释：
第 0 分钟开始时，怪物的距离是 [1,1,2,3]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,1,2]，你输掉了游戏。
你只能消灭 1 个怪物。
输入：dist = [3,2,4], speed = [5,3,2]
输出：1
解释：
第 0 分钟开始时，怪物的距离是 [3,2,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,2]，你输掉了游戏。
你只能消灭 1 个怪物。
解题思路:
贪心 + 排序
先补充个知识点:
贪心算法:（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
这道题我们按照题意硬翻译的话不太好处理, 那么我们可以转换下思路
首先因为一直每只怪兽初始距离dist[i], 初始速度speed[i], 那么消灭每个怪兽到达城市最小时间为: dist[i] / speed[i]
例如: 初始距离2, 速度1, 我们需要 2 / 1 = 2分钟时候消费怪兽, 对吗? 这么想就错了!!! 2分钟再开火, 怪兽都骑到脸上了, 直接GG。要在1分钟时候将其消灭
实际上最小消灭时间应该为: (dist[i] - 1) / speed[i]
那么我们依次计算出每个怪兽应该消灭最小时间time数组, 做一次正序排列
再依次循环time数组, 判断time[i] - i是否小于0
例如:
时间数组 time 为 [0, 1, 2], 那么我们
- 第0分钟消灭到达时间为0的怪兽
- 第1分钟消灭到达时间为1的怪兽
- 第2分钟消灭到达时间为2的怪兽
故满足
dist[i]: [1, 1, 3], speed[1, 1, 1]
时间数组 time 为 [0, 0, 2], 那么我们
- 第0分钟消灭到达时间为0的怪兽
但是在1分钟实际上有2只到达, 我们同一时间点只能消灭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 {
// 定义结果res, 空数组time, 用来存放最小消灭时间
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;
}
// 满足 消灭结果 + 1
res += 1
}
// 返回 最大消灭数量res
return res;
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
网友评论