算法笔试模拟题精解之“移动射击”

简介: 首先理解题意,题目说的“发动之后只能改变一次方向”是干扰你的,因为即使你在中间过程中左右摆,但宏观上还是最多改变了一次方向。

在线编程介绍

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

看完之后是不是有了想法了呢,题目直达链接:查看题目:移动射击
720-150.png

相关文章
|
6月前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
60 0
|
6月前
|
编解码 算法 前端开发
往年 | 大疆雷达算法校招笔试题目解析
往年 | 大疆雷达算法校招笔试题目解析
483 1
|
算法
压缩算法 【腾讯2020校园招聘-后台&综合-第一次笔试 】
压缩算法 【腾讯2020校园招聘-后台&综合-第一次笔试 】
86 0
|
算法 网络协议
骚戴独家笔试---算法篇4
骚戴独家笔试---算法篇4
62 1
|
存储 算法
骚戴独家笔试---算法篇3
骚戴独家笔试---算法篇3
203 0
骚戴独家笔试---算法篇3
|
搜索推荐
7大排序算法-- 堆排 快速排序 --精解(下)
7大排序算法-- 堆排 快速排序 --精解(下)
84 0
|
搜索推荐
7大排序算法-- 堆排 快速排序 --精解(上)
7大排序算法-- 堆排 快速排序 --精解
52 0
|
搜索推荐 算法
7大排序算法-- 直接插入,希尔,冒泡,选择 --精解(下)
7大排序算法-- 直接插入,希尔,冒泡,选择 --精解(下)
130 0
|
存储 搜索推荐
7大排序算法-- 直接插入,希尔,冒泡,选择 --精解(上)
7大排序算法-- 直接插入,希尔,冒泡,选择 --精解
84 0
|
算法 Serverless 测试技术
骚戴独家笔试---算法篇5
骚戴独家笔试---算法篇5
57 0