C. 小红打怪 (python解)-牛客
原题链接:
问题分析:
- 小红的全体打击技能对所有怪物造成1点伤害。
- 队友1的单体打击技能可以对任意单个怪物造成1点伤害。
- 队友2的范围攻击技能可以对相邻的两只怪物分别造成1点伤害(可对已死亡的怪物使用)。
思路:
- 设定一个函数
check(mx)
用来验证在mx
次攻击下,是否可以击杀所有怪物。 - 首先使用小红的技能,在每个回合中每个怪物的生命值减少
mx
。 - 使用队友的技能来补充对生命值仍然大于零的怪物的攻击。
- 我们可以使用二分法来寻找能够击杀所有怪物的最小回合数。即在
0
到10^14
之间进行查找。 - 通过
check(mx)
函数判断当前回合数是否足够。 - 直接计算每个技能的应用结果,避免不必要的数组复制,提高效率。
代码:
def main():
n = int(input())
a = list(map(int, input().split()))
def check(mx):
k1, k2 = mx, mx # 小红和队友2的技能可用次数
hp = a.copy() # 剩余血量
# 小红攻击
for i in range(n):
hp[i] = max(0, hp[i] - mx)
# 队友2的范围攻击
for i in range(n - 1):
if hp[i] > 0 and hp[i + 1] > 0:
t = min(hp[i], hp[i + 1], k2)
k2 -= t
hp[i] -= t
hp[i + 1] -= t
# 验证剩余血量是否可以用队友1的单体攻击击杀
return sum(hp) <= k1 + k2
left, right = 0, 10 ** 14
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid
return right
print(main())
标签:牛客,python,hp,小红,打怪,队友,怪物,mx,技能
From: https://www.cnblogs.com/666-777-eto/p/18538271