牛客真题编程——day2

编程环境：java

1、回合制游戏

描述

你在玩一个回合制角色扮演的游戏。现在你在准备一个策略，以便在最短的回合内击败敌方角色。在战斗开始时，敌人拥有HP格血量。当血量小于等于0时，敌人死去。一个缺乏经验的玩家可能简单地尝试每个回合都攻击。但是你知道辅助技能的重要性。
在你的每个回合开始时你可以选择以下两个动作之一：聚力或者攻击。
    聚力会提高你下个回合攻击的伤害。
    攻击会对敌人造成一定量的伤害。如果你上个回合使用了聚力，那这次攻击会对敌人造成buffedAttack点伤害。否则，会造成normalAttack点伤害。
给出血量HP和不同攻击的伤害，buffedAttack和normalAttack，返回你能杀死敌人的最小回合数。

算法思路：

这道题的逻辑比较简单，根据题目意思，只需分情况处理即可。当normal攻击的2倍>=buff攻击时，相当于求对Hp/normal的倍数；否则（<时），Hp/buff如果整除，表明只需攻击Hp/buff*2次，当余数＜nor时次数加1，否则次数加2.要注意的是整型的除法的向下舍入问题。

部分代码实现：

2、大整数相乘

描述：

有两个用字符串表示的非常大的大整数,算出他们的乘积，也是用字符串表示。不能用系统自带的大整数类型。

算法思路：

    大整数的字符串相乘，可以把它们拆分成竖式计算。对每一位的数字分别对应相乘，找到相乘的结果与整体结果之间的关系(索引与结果之间的位置关系)，将每次相乘的结果加到最终结果的整型数组中。然后根据输出要求，将其转换为字符串输出。

逻辑关系：num1中的第i位与num2中的第j位，他们的结果占第i+j位和第i+j+1位

如图，将所有的结果累加在结果数组res中，res设一个自增长的vector数组。

3、六一儿童节

描述：

六一儿童节，老师带了很多好吃的巧克力到幼儿园。每块巧克力j的重量为w[j]，对于每个小朋友i，当他分到的巧克力大小达到h[i] (即w[j]>=h[i])，他才会上去表演节目。老师的目标是将巧克力分发给孩子们，使得最多的小孩上台表演。可以保证每个w[i]> 0且不能将多块巧克力分给一个孩子或将一块分给多个孩子。

算法思想：

     对巧克力和儿童从小到大排序，以巧克力为索引依次遍历，当巧克力<=孩子需求时，则可以上台，人数加一。当所有的孩子遍历完成后，提前退出循环，防止重复的计数。

代码部分实现：

algorithm库sort函数