在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的第75题：移动射击 的题目解析，具体如下：

题目描述

题目等级：中等
知识点：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.

看完之后是不是有了想法了呢，题目直达链接：查看题目：移动射击