| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5128 人关注过本帖, 2 人收藏
标题:笔试时候遇到的一道神题!还是最近才出的,出题者肯定是星战迷,我给gui了. ...
取消只看楼主 加入收藏
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
结帖率:0
收藏(2)
已结贴  问题点数:20 回复次数:11 
笔试时候遇到的一道神题!还是最近才出的,出题者肯定是星战迷,我给gui了...
偷偷拍照手打了一份,大家看看:

死星之战(一)
卢克在死星上面遭遇到一队敌人的进攻,每个敌人有两个属性:healthy(生命值) 和 attack(攻击力),卢克有把激光剑,激光剑每次除了对锁定的敌人造成固定伤害之外,同时还能对其他敌人产生5%的群伤溅射效果。卢克每次锁定攻击一个敌人(被锁定的敌人死亡之前,卢克不能更换攻击对象),但是其他敌人可以同时攻击卢克;所有人的攻击速度都相同;现在要写一个函数来找出一个最优的顺序来杀死这些敌人,而让卢克受到的伤害最小。
输入参数:
二维数组,表示敌人的healthy 和 attack,如: [[10, 2], [20, 1], [8, 6], [1, 1]]
卢克的攻击力,整数,如 3
输出:
在输入的二维数组中调整敌人的顺序,index 为 0 的最先被攻击,以此类推。
(注:编程语言不限)

搜索更多相关主题的帖子: 激光 攻击力 
2016-01-18 14:18
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
应该是要先把攻击高的干掉吧?卢克每次只能打一个,而敌人是群殴,如果先打攻击少的,高攻击的每回合都会打卢克,回合越多就越亏。
2016-01-18 14:26
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
回复 4楼 rjsp
那应该跟卢克的攻击、敌人的血量也有关系
2016-01-19 10:27
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
回复 6楼 wmf2014
暴力破解法,应该是一种简单有效的思路了!
2016-01-21 10:46
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
跟认识的一些大神做了讨论,如果不考虑5%的群伤,解题思路可以是这样的:
比较相邻两个敌人不同顺序对卢克造成的攻击大小,然后做个冒泡排序,就可以得出最终的排序。
假设:
卢克的攻击为A,敌人攻击、血量为(a1,h1)、(a2,h2)、...

ceil()为向上取整函数,卢克杀死敌人1的回合数为ceil(h1/A),同理杀死敌人2的回合数为ceil(h2/A)...
为了易于表述,姑且将ceil(h1/A)直接用h1/A表示。

第一种排序:[(a1,h1),(a2,h2)]
卢克受到的伤害值为:[(a1+a2)*(h1/A)] + [a2*(h2/A)]
解释:第一个中括号是第一个敌人存活期间,一共对卢克造成的总伤害;第二个中括号,是第二个敌人对卢克造成的伤害;

第二种排序:[(a2,h2),(a1,h1)]
卢克受到的伤害值为:[(a2+a1)*(h2/A)] + [a1*(h1/A)]

两者一比较,相同项去掉,第一种排序剩余:a2*(h1/A),第二种排序剩余:a1*(h2/A)
这两个值,谁大就说明伤害多。以这种方式冒泡,就可以得出排序。
-------------------
不过,加上了5%的群伤...就太复杂了,目前能想到的方式,就是暴力破解,把每种排序组合都计算一遍,然后排序...
2016-01-24 18:46
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
以下是引用beyondyf在2016-1-23 16:24:47的发言:

题目的描述本身有很多模糊的地方,不过不影响解题模型的构建。这里简单说一下我的思路。

每个敌人以卢克的第几次攻击开始锁定它,则它对卢克造成的伤害可以用f(i,j)表示。i表示敌人的序号,j表示它从卢克的第j次攻击开始被锁定。

每个敌人对卢克的伤害只与他被锁定的时间有关,与其他敌人无关。由f函数可以形成一个二维矩阵,现在问题转化成从每一行里挑一个数加起来使得总值最小的问题。从而可用分组背包来解。


但是,敌人有可能还没被锁定,就已经死了?
我没理解到大神的意思,这个二维矩阵是个什么东东...
2016-01-24 19:02
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
以下是引用lianyicq在2016-1-22 10:30:04的发言:

问题的目标函数,评价函数都很容易得到,解空间也很清晰。看看模拟退火的应用吧。



模拟退火...不明觉厉,研究看看先
2016-01-24 19:10
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
以下是引用菜鸟2016在2016-1-21 11:08:22的发言:

想知道是哪路神仙出的这神题啊?本人菜鸟,但是请教了公司几位前辈,都无解啊。。。。。


一个叫瑞数信息的公司,好像没成立多久,搞网络安全的,貌似里面牛人比较多。待遇给的倒是不错,可惜我笔试都没过 哈哈
网上有招聘信息,可以自己搜
2016-01-24 19:14
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
回复 26楼 TonyDeng
啊?为啥是皮包公司
我感觉挺正规的啊
2016-01-25 17:50
mic_zhang
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2016-1-18
收藏
得分:0 
回复 29楼 TonyDeng
哈哈 网站果然有点山寨,基本没有内容,我之前都没看过
我是去公司面试的,办公室还要山寨一点,貌似跟别的公司合租的,在成都软件园A8
不过面试时给我解释过,说这个是暂时的,马上要搬到E区的长虹科技大厦去,那边办公室在装修。
从面试官及HR来看,感觉还是很有水平的

创业公司是这样的,我之前也投过不少这种小公司了,很多主页都没有,还有很多办公室是在家属区里面的...我之前的一个公司就是
2016-01-25 18:57
快速回复:笔试时候遇到的一道神题!还是最近才出的,出题者肯定是星战迷,我给g ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.012976 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved