娱乐 每 日 算 法 挑 战 【第E期】

[yhz012]

来了来了，让我看看，给我点时间先刷个牙

 

那你很勇哦.jpg

 

首先一些最基本的计算可以得到：

不吃药情况下：怪物回合数 T = floor(L / D)

因此受到的伤害是 T * L

 

每喝一瓶大力就相当于少一次怪物出手的机会

所以感觉已经能贪心了？

 

艹不对，我傻了，可能因为取整情况有影响……不过贪就完了应该没问题

 

不对，我是真的傻了，每一瓶一定只减少1次怪物回合（除非到0），所以直接贪应该就可以了？

四月 26, 2020，由yhz012修改
不要边刷牙边想问题

[yhz012]

刚刚, Mr.K 018 说道:

我超勇的！

以防万一我确认下，战斗中嗑药不算回合的吧？

[yhz012]

3 小时前, Mr.K 018 说道:

不算，这一点可以放心

那我觉得今天问题直接贪就可以了？

 

首先如果不吃药，怪物回合数 T_i = floor(L_i / D)，受到的伤害 dH_i = T_i * K_i

 

吃药情况下，除了把大力理解为增加下一次攻击的方式，另一种理解方法是怪物看到了K018喝大力的姿势非常勇所以张嘴闭眼震惊到无法行动一回合。也就是怪物少出手了一回合。当然多喝几瓶就多白嫖几回合

 

而我们的目的是让K018不死，换另一个角度考虑可以理解为是找到完成任务所受到的最少伤害

因为整个魔塔没有加攻或者加血什么的复杂机制，都是超勇的直接对日，那么很显然好钢用在刀刃上，如果一个怪打我很疼，那么我就要超勇的喝大力。只要我秒了他，那他就没得出手了。（所以实际上如果一场战斗我注定要喝大力的话，那我不如先喝为敬

 

所以算法就很显然了（施工中

import numpy as np

T = np.floor(L / D) #各怪回合数
idx = list(np.argsort(K)) #根据怪物攻击力升序排列

for i in reversed(idx): #从最疼的怪开始
	dm = min(T[i], m) #大力能喝多少喝多少
	m = m - dm #喝掉大力
	T[i] = T[i] - dm #白嫖回合
	if m == 0: #大力喝光了
		break

dH = np.sum(T * K) #统计受到的总伤害

return H > dH

 

四月 26, 2020，由yhz012修改
忘了删施工中的标注了

[yhz012]

4 分钟前, Mr.K 018 说道:

基本上就是这样的。这道题的关键就在于大力的作用看上去是加攻击力，但实质是沉默对面一回合

这个题其实是2019BIT校赛的一道题，我拿不到题面于是就另编了一个

是的，初看起来毕竟吓唬人，实际上注意到这一点之后会变得很简单

外加上因为怪物本身实际上可以理解为不存在先后顺序（因为不涉及到影响男主攻击力和血量还有大力储量的问题），所以就能确保局部最优就是全局最优，直接贪就可以了