#P4550. 第2题-塔防游戏
-
1000ms
Tried: 43
Accepted: 14
Difficulty: 6
所属公司 :
华为
时间 :2026年1月21日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>贪心算法
第2题-塔防游戏
解题思路
题目中每个敌人以恒定速度向基地移动,你的武器初始已充满能量,并且每分钟开始时(第 0、1、2... 分钟)最多可以消灭 1 个敌人;若某个敌人在某一分钟开始时已经到达基地(距离 ≤ 0),它会先攻击基地,游戏立刻结束。
把每个敌人“最晚还能撑到第几分钟开始前不到达基地”转成一个时间点:
- 敌人到达基地的时间是
dist[i] / speed[i](实数) - 若它恰好在整数分钟
t到达,则在第t分钟开始你还没来得及开枪就输了 - 因此我们用“到达的最早整数分钟”表示危险时刻:
time[i] = ceil(dist[i] / speed[i]) = (dist[i] + speed[i] - 1) / speed[i]这表示敌人会在第time[i]分钟开始前到达/或恰好到达并导致失败,你必须在分钟0..time[i]-1之间某一刻消灭它。
算法(贪心 + 排序):
- 计算每个敌人的
time[i] - 将
time升序排序(越早到达越先处理) - 从第 0 分钟开始依次消灭:如果排序后第
k个敌人的time[k] <= k,说明它在你第k次开枪前就已到达(或恰好到达并先攻击),游戏结束;否则可以消灭并继续。
复杂度分析
- 时间复杂度:
O(n log n)(排序) - 空间复杂度:
O(n)(存储到达时间数组) 满足n <= 1e5的数据范围。
代码实现
import sys
def max_kill(dist, speed):
# 计算每个敌人到达基地的最早整数分钟 time = ceil(dist/speed)
times = [(d + s - 1) // s for d, s in zip(dist, speed)]
times.sort() # 贪心:按到达时间从早到晚处理
# 第 k 分钟开始进行第 k 次消灭(k 从 0 开始)
for k, t in enumerate(times):
# 若 t <= k,表示敌人在第 k 分钟开始前/恰好开始时到达,来不及消灭
if t <= k:
return k
return len(times)
def main():
data = list(map(int, sys.stdin.read().strip().split()))
n = data[0]
dist = data[1:1 + n]
speed = data[1 + n:1 + 2 * n]
print(max_kill(dist, speed))
if __name__ == "__main__":
main()
#include <bits/stdc++.h>
using namespace std;
// 题面功能:返回最多能消灭的敌人数
int maxKill(const vector<int>& dist, const vector<int>& speed) {
int n = (int)dist.size();
vector<int> times(n);
// time = ceil(dist/speed) = (dist + speed - 1) / speed
for (int i = 0; i < n; i++) {
times[i] = (dist[i] + speed[i] - 1) / speed[i];
}
sort(times.begin(), times.end()); // 贪心:先处理最早到达的敌人
for (int k = 0; k < n; k++) {
// 第 k 分钟开始进行第 k 次消灭
// 若 times[k] <= k,则敌人已到达/恰好到达导致失败
if (times[k] <= k) return k;
}
return n;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> dist(n), speed(n);
for (int i = 0; i < n; i++) cin >> dist[i];
for (int i = 0; i < n; i++) cin >> speed[i];
cout << maxKill(dist, speed) << "\n";
return 0;
}
import java.util.*;
public class Main {
// 题面功能:返回最多能消灭的敌人数
static int maxKill(int[] dist, int[] speed) {
int n = dist.length;
int[] times = new int[n];
// 计算每个敌人到达基地的最早整数分钟:time = ceil(dist/speed)
for (int i = 0; i < n; i++) {
times[i] = (dist[i] + speed[i] - 1) / speed[i];
}
// 贪心:按到达时间从早到晚处理
Arrays.sort(times);
// 第 k 分钟开始进行第 k 次消灭(k 从 0 开始)
for (int k = 0; k < n; k++) {
// 若 times[k] <= k,表示敌人在你开枪前已到达/恰好到达,游戏结束
if (times[k] <= k) return k;
}
return n;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] dist = new int[n];
int[] speed = new int[n];
// 输入 dist
for (int i = 0; i < n; i++) dist[i] = sc.nextInt();
// 输入 speed
for (int i = 0; i < n; i++) speed[i] = sc.nextInt();
System.out.println(maxKill(dist, speed));
}
}
题目描述
你在玩一款塔防游戏,需要操控堡垒保护基地免收敌人袭击。
敌人与基地的距离由大小为 n 的整数数组 dist 表示,其中 dist[i] 是第 i 个敌人与基地的距离(单位为 km)。
敌人会以恒定的速度冲向基地,速度由大小为 n 的整数数组 speed 表示,其中 speed[i] 是第i个敌人的速度(单位为 km/min)。
你的堡垒有一种充能武器,该武器:
- 需要 1 分钟进行充能,一旦充满能量即可无视距离击杀一个敌人。
- 该武器在游戏开始时为充满能量的状态。
游戏规则如下
- 敌人从第 0 分钟开始移动,一旦有一个敌人抵达城市,游戏结束;
- 如果某个敌人刚好在某一分钟开始时抵达城市,他会在你的堡垒可以使用武器前攻击基地,游戏结束;
- 如果所有敌人在到达基地前被击杀,游戏结束。
输入
- 第一行为正整数
n,表示敌人的数量; - 第二行为整数数组
dist,表示敌人的初始距离,有n个元素,中间以空格隔开,且 1 <=dist[i]<= 105; - 第三行为整数数组
speed,表示敌人的速度,有n个元素,中间以空格隔开,且 1 <=speed[i]<= 20; n = dist.length = speed.length;- 1 <= n <= 105。
输出
一个正整数,表示游戏结束前可以消灭的最大数量。
样例 1
输入:
3
1 4 4
5 2 3
输出:
2
解释:
-
第 0 分钟开始,敌人的距离为 [1,4,4],第一个敌人距离基地最近,消灭了第一个敌人;
-
第 1 分钟开始,敌人的距离为[X,2,1],第三个敌人距离基地最近,消灭了第三个敌人;
-
第 2 分钟开始,敌人的距离为 [X,0,X],第二个敌人抵达基地,游戏结束。
击杀了 2 个敌人。
样例 2
输入:
3
1 2 3
1 1 1
输出:
3
解释:
-
第 0分钟开始,敌人的距离为 [1,2,3],第一个敌人距离基地最近,消灭了第一个敌人;
-
第 1 分钟开始,敌人的距离为 [X,1,2],第二个敌人距离基地最近,消灭了第二个敌人;
-
第2分钟开始,敌人的距离为 [X,X,1],只剩下第三个敌人,消灭了第三个敌人。
击杀了 3个敌人。