Viego最优击杀敌人算法实现：求解最短击杀时间

Viego是一名强力英雄，需在战斗中击杀所有敌人。他拥有一项魔法，使用规则如下：

• 选择一名敌人，对其造成damage点伤害。
• 若击杀敌人，魔法将部分充能，可在下一秒再次使用，但伤害减少damageReduction点，该机制可多次生效，伤害最低为0（也可放弃该机会，重新准备魔法）。
• 准备魔法需5秒，施法不耗时。

时间以秒为单位，Viego可在第0秒初始时刻直接施法。请设计最优方案，让Viego以最少时间击杀所有敌人，只需实现以下函数返回最短时间即可。

函数定义 #

def bestKillingPlan(damage: int, damageReduction: int, enemies: List[int]) -> int:
    pass

测试用例 #

test_case = [
{'damage':100, 'damageReduction': 22, 'enemies':[98], 'answer':0},
{'damage':100, 'damageReduction': 17, 'enemies':[236], 'answer':10},
{'damage': 10, 'damageReduction':  3, 'enemies':[10, 7, 4, 1], 'answer':3},
{'damage':300, 'damageReduction':100, 'enemies':[400,300,300], 'answer':7},
{'damage':500, 'damageReduction':100, 'enemies':[900,500,400,200,300], 'answer':9}
]

第4个测试用例可行方案示例 #

seconds|enemy_index
      0|          1
      1|          0
      6|          2
      7|          0

内容的提问来源于stack exchange，提问作者wangjianyu