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

[Mr.K 018]

前两天事情有点多，（连电脑都没时间开），于是鸽了一天x

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

第14期 【大力】出奇迹

这是一个很老套的故事：有一个回合制的RPG游戏，里面有一个可以拿装备/道具/塞尔逵公主的副本，副本里有若干怪物，想要拿到奖励就得把怪物一一打倒才行。我们的主人公K018打算下这个副本。这个B非常勇，他决定不带回血的药也不练回复技能，就硬莽。他出发之前掂量了一下自己的斤两，觉得就这么莽多半是直接凉凉。但是已经说过不带药和回复技能了，怎么办呢？

他思来想去，决定找天桥的某位“药剂供应商”买一点【大力】。这位天桥药剂供应商向他保证：只要吃一份【大力】，下次攻击的伤害就能超级加倍！听了这话我们的主人公K018激动地当场买下了他能买下的全部【大力】，然后就准备下副本了。

已知K018的血量H和攻击伤害D，每一个怪物的血量L_i和攻击伤害K_i，以及我们主人公K018持有的【大力】数量。

主人公每吃下一份【大力】，下一次攻击的伤害就增加D。例如某次攻击前他一口气吃下了10份【大力】，那么这次攻击他就能打出11D的伤害！不过，如果下次攻击前没有继续吃【大力】的话，那仍然只能打出D的伤害。当然，怪物不会蠢到去天桥买【大力】，所以怪物是没有的。同时，由于K018非常勇，所以跟怪物交手时总是他先出手。

我们的主人公K018觉得他彳亍了。各位算算看，他真的彳亍吗？

输入

第一行有三个整数H, D, m和n。H表示K018的血量，D表示K018的攻击伤害，m表示他持有【大力】的份数，n表示怪物数量。

接下来n行，每行两个整数L_i和K_i，分别表示第i个怪物的血量和攻击伤害。

提示：主角和怪物是轮流攻击的直到有一方被打倒为止。主角一次只面对一个怪物。

输出

如果K018能做到在被打倒（血量小于等于0）前打倒所有怪物，就输出一行“彳亍”，否则输出一行“不彳亍”。

 

有一说一，只吃一份【大力】攻击伤害确实能翻倍，天桥卖大力的倒也没说假话

[吃橙子啊]

好有趣但是 我完全不会

感觉和魔塔游戏好像
在这里插个眼等大佬~

[yhz012]

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

 

那你很勇哦.jpg

 

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

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

因此受到的伤害是 T * L

 

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

所以感觉已经能贪心了？

 

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

 

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

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

[Mr.K 018]

16 分钟前, yhz012 说道:

那你很勇哦.jpg

我超勇的！

[yhz012]

刚刚, Mr.K 018 说道:

我超勇的！

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

[Mr.K 018]

1 分钟前, yhz012 说道:

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

不算，这一点可以放心

A上去之前喝一吨大力也不占回合的（察觉）

四月 26, 2020，由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修改
忘了删施工中的标注了

[Mr.K 018]

3 分钟前, yhz012 说道:

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

 

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

 

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

 

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

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

 

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

import numpy as np

 

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

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

[yhz012]

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

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

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

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

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