LCP 30. 魔塔游戏

题目

原题链接

LCP 30. 魔塔游戏

思路

1. 如果nums的和加起来小于零的话，那么不管怎么选择都不可能全部访问完，大于零的话是一定有解得；
2. 大于零就加血，小于零就扣血，但如果血量小于 1，从前面的扣血中，拿出一个扣血量最大的数也就是pq.push(-nums);移到数组的末尾，把之前扣掉的血重新加回来

优先级队列

//升序队列  小根堆 great 小到大
priority_queue<int,vector<int>,greater<int>> pq;

//降序队列  大根堆 less  大到小 默认
priority_queue<int,vector<int>,less<int>> pq1;
priority_queue<int> pq2;

代码

class Solution 
{
   
public:
    int magicTower(vector<int>& nums) 
    {
   
    	//先判断一下有没有解
        int sum = 0;
        for(auto e:nums) sum += e;
        if(sum < 0) return -1;

        int res = 0;//结果
        int hp = 1;//血线
        priority_queue<int> pq;//大根堆
        for(auto e:nums)
        {
   
            if(e < 0) pq.push(-e);

            hp += e;
            if(hp < 1)
            {
   
            	//这意味着 e < 0，前面会把 e 入堆
                hp += pq.top();//之前扣得最多的血加回来
                pq.pop();
                res ++;
            }
        }
        return res;

    }
};