1921. 消灭怪物的最大数量
1921. 消灭怪物的最大数量
你正在玩一款电子游戏,在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ,其中 dist[i] 是第 i 个怪物与城市的 初始距离(单位:米)。
怪物以 恒定 的速度走向城市。给你一个长度为 n 的整数数组 speed 表示每个怪物的速度,其中 speed[i] 是第 i 个怪物的速度(单位:米/分)。
怪物从 第 0 分钟 时开始移动。你有一把武器,并可以 选择 在每一分钟的开始时使用,包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人,一次可以消灭任一还活着的怪物。
一旦任一怪物到达城市,你就输掉了这场游戏。如果某个怪物 恰 在某一分钟开始时到达城市,这会被视为 输掉 游戏,在你可以使用武器之前,游戏就会结束。
返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭,返回 n 。
示例 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],你消灭了第三个怪物。
所有 3 个怪物都可以被消灭。
示例 2:
输入:dist = [1,1,2,3], speed = [1,1,1,1]
输出:1
解释:
第 0 分钟开始时,怪物的距离是 [1,1,2,3],你消灭了第一个怪物。
第 1 分钟开始时,怪物的距离是 [X,0,1,2],你输掉了游戏。
你只能消灭 1 个怪物。
示例 3:
输入:dist = [3,2,4], speed = [5,3,2]
输出:1
解释:
第 0 分钟开始时,怪物的距离是 [3,2,4],你消灭了第一个怪物。
第 1 分钟开始时,怪物的距离是 [X,0,2],你输掉了游戏。
你只能消灭 1 个怪物。
对于这一题,其实博主觉得对于大多数人来说可能比较难,因为很多编程问题其实是可以套模板的,套模板然后解题,对于很多人可能变成了思维模式,但是对于这一题,博主觉得可能没有什么模板可套的,问题过于特殊化,解题代码如下:
int eliminateMaximum(int* dist, int distSize, int* speed, int speedSize){
int arrive_time[distSize];
int max=0;
for(int i=0;i<distSize;i++){
arrive_time[i]=dist[i]/speed[i]+(dist[i]%speed[i]?1:0);
max=fmax(max,arrive_time[i]);
}
max=max+1;
int dp[max];
for(int i=0;i<max;i++){
dp[i]=0;
}
for(int i=0;i<distSize;i++){
dp[ arrive_time[i]]++;
}
int count=1;
int i;
int sum=0;
int pre=0;
for( i=1;i<distSize+1;i++){
if(dp[i]!=0){
if(dp[i]>count){
return i;
break;
}
else{
pre=i;
count=count-dp[i];
}
}
count++;
}
return distSize;
}
相关文章
- 2022-11-01:给定一个只由小写字母和数字字符组成的字符串str。 要求子串必须只含有一个小写字母,数字字符数量随意。 求这样的子串最大长度是多少?
- 你知道线程池的 创建方式、7大参数、处理流程 和 最大线程数量该如何配置吗
- 【每日要闻】台积电超过三星成全球最大半导体销售公司;iPhone 14系列创首发最快降价纪录
- AlDente for Mac(mac电池最大充电限制工具)
- 迄今最大暗物质地图绘成 覆盖南半球1/4天空
- 变脸 MySQL:单实例最大支持表数量(mysql最大表数)
- 值提升MySQL ID最大值的方法(mysqlid最大)
- Redis:设置最大数量限制(redis数量上限)
- Redis应用最大容量:突破极限(redis数量上限)
- Redis: 最大容足量数之极限(redis数量上限)
- 20个争议最大的编程观点,你认可几点?
- Oracle超大型进程数量极限探究(oracle最大进程数)
- SQL Server极限挑战:最大列数量突破(sqlserver列数量)
- 深入理解Oracle查询结果集:取得最大技术优势(oracle查询结果集)
- 如何配置Redis最大内存空间(怎么看redis最大内存)
- Oracle数据库系统最大可支持的会话数量(oracle会话最大数)
- Redis中频道最大容量究竟是多少(redis 频道最大数量)
- Redis如何设定长连接的最大数量(redis长连接最大数量)
- Redis键长度之最长实践(redis键最大长度)
- Oracle数据库中一行最大字符数的限制(oracle一行最大长度)
- Redis最大IP连接数不得超过预期(redis连接ip数量)