算法笔试模拟题精解之“移动射击”
算法笔试模拟题精解之“移动射击”
贡献者 | 张鹏飞
简介：首先理解题意，题目说的“发动之后只能改变一次方向”是干扰你的，因
为即使你在中间过程中左右摆，但宏观上还是最多改变了一次方向。
题目描述
题目等级：中等
知识点：DP
查看题目：移动射击
你正在数轴上跟小精灵对战。你拥有一个十分强力的技能称为移动射击，但是这
个技能有一个缺点是在你发动之后只能改变一次方向。
你可以认为你的位置在数字 0 的位置上，在数轴的正方向上有 n 只精灵，负方向
上有 m 只精灵。移动射击可以造成 w 点伤害。每个精灵都有自己的血量，当血量降
为 0 时死亡。
在最开始时你可以选择向正方向或负方向释放移动射击，并且可以在任意时刻改
变技能的方向。请问你最多可以击杀多少只小精灵 ?(n，m，w 以及精灵的血量均在
[1, 100000] 范围内 )
输入内容为五个，前三个为三个数字：正方向上的精灵个数 n、负方向上的精灵
个数 m, 移动射击可以造成的伤害 w；第四个是一个长度为 n 的数组 a，表示正方向
上的 n 个精灵的血量；第五个是一个长度为 m 的数组 b，表示负方向上的 m 个精灵
的血量。
输出一个数字，表示最多能够击杀的精灵数量。
示例 1
输入：
3
4
10
[1, 2, 3]
[4, 3, 2 ,1]
输出：
4
解题思路
大致思路：首先理解题意，题目说的“发动之后只能改变一次方向”是干扰你
的，因为即使你在中间过程中左右摆，但宏观上还是最多改变了一次方向。
如果说：我先杀左边一个，然后转头杀右边一个，再转头杀左边三个，又回头杀
右边 1 个，看起来是不是改变了三次方向，其实呢，相当于我先杀左边四个，再回头
杀右边两个，效果是一样的。因为你想这个问题的时候，可以忽略这个限制。
具体过程：先遍历数组 a，a[i] 表示数组 a 前 i 个数的和，当 a[i]>=w 的时候，记
住此时的位置 index_a=i，退出循环，退出后加上这句 if(i==n||a[i]>w) index_a--;
因为 index_a 指向的是刚好不超过 w 的位置，而且不能越界。
对 b 数组也是如此，然后开始从 index_a 往后一步一步走 ;
走一步，看看 b 数组的情况，k 为 b 数组的下标，初始 k=0;
while(k<m &&a[i]+b[k]<=w) k++;
然后和当前最长的长度比较
ans=Math.max(ans,i+k+1);
当 index_a 一直走到底，可返回 ans.
看完之后是不是有了想法了呢，题目直达链接：查看题目：移动射击
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”