怪物一半血量 AOE 伤害最少次数问题

问题描述

1.若干怪物的血量是正整数，怪物血量变为0时判定死亡。

2.玩家单次攻击可以对一个怪物造成一点伤害

3.怪物生命值削减到最大生命值一半时会对所有怪物造成一点伤害

给一个算法，输入一个整形数组代表怪物的血量，求令所有怪物死亡的最少攻击次数。

解题思路：

1. 我们需要考虑两种伤害来源：

   • 玩家的直接攻击（每次1点伤害）
   • 怪物达到一半血量时的溅射伤害（对所有怪物造成1点伤害）

2. 关键点：

   • 当一个怪物血量降到一半时会触发群体伤害，这可能比单独攻击更有效
   • 需要找到最优的攻击顺序来最大化溅射伤害的效果

3. 解决方案：

   • 使用贪心策略，优先选择触发溅射伤害最有利的目标
   • 每次选择当前血量最高的怪物进行攻击
   • 记录每次溅射伤害的效果

这是实现代码：

def minAttacks(monsters):
    n = len(monsters)
    if n == 0:
        return 0
        
    # 计算触发溅射伤害的血量
    def getTriggerHP(hp):
        return (hp + 1) // 2
    
    # 拷贝原数组
    hp = monsters.copy()
    attacks = 0
    
    while True:
        # 检查是否所有怪物都已死亡
        if all(h <= 0 for h in hp):
            return attacks
            
        # 找到当前血量最高的怪物
        max_hp = max(hp)
        max_idx = hp.index(max_hp)
        
        if max_hp <= 0:
            break
            
        # 计算触发溅射伤害的血量
        trigger_hp = getTriggerHP(monsters[max_idx])
        
        # 如果当前血量大于触发血量，继续攻击
        if hp[max_idx] > trigger_hp:
            hp[max_idx] -= 1
            attacks += 1
        # 如果刚好达到触发血量，造成群体伤害    
        elif hp[max_idx] == trigger_hp:
            # 对所有怪物造成1点伤害
            for i in range(n):
                hp[i] = max(0, hp[i] - 1)
            attacks += 1
        # 如果低于触发血量，直接攻击至死亡
        else:
            attacks += hp[max_idx]
            hp[max_idx] = 0
            
    return attacks

示例使用：

# 测试用例
test_cases = [
    [3, 3],           # 输出: 4
    [4, 2, 1],       # 输出: 4
    [10, 5, 3],      # 输出: 12
]

for case in test_cases:
    print(f"怪物血量: {case}")
    print(f"最少攻击次数: {minAttacks(case)}")
    print()

算法说明：

1. 每次选择血量最高的怪物进行攻击
2. 如果当前血量高于触发血量，继续单体攻击
3. 如果达到触发血量，造成群体伤害
4. 如果低于触发血量，直接攻击至死亡
5. 重复以上步骤直到所有怪物死亡

复杂度分析：

• 时间复杂度：O(H * N)，其中H是最大血量，N是怪物数量
• 空间复杂度：O(N)，需要存储怪物血量的副本

这个算法可以有效地处理各种情况，并找到最少的攻击次数。