LCP30.魔塔游戏

链接：LCP30.魔塔游戏
难度：Medium
标签：贪心、数组、堆（优先队列）
简介：小扣初始血量为 1，且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪，为保证血量始终为正值，小扣需对房间访问顺序进行调整，每次仅能将一个怪物房间（负数的房间）调整至访问顺序末尾。请返回小扣最少需要调整几次，才能顺利访问所有房间。若调整顺序也无法访问完全部房间，请返回 -1。

题解 1 - python

• 编辑时间：2024-02-06
• 执行用时：109ms
• 内存消耗：30.9MB
• 编程语言：python
• 解法介绍：对遍历过的负数进行记录，如果打不过，就拿出前面最大的负数放到后面。

class Solution:
    def magicTower(self, nums: List[int]) -> int:
        q = []
        cur = 1
        ans = sum = 0
        for num in nums:
            if num < 0: heappush(q, num)
            while q and cur <= -num:
                ans += 1
                top = heappop(q)
                cur -= top
                sum += top
            if cur <= -num: return -1
            cur += num
        return ans if cur > -sum else -1