专业网站设计的网站,wordpress 淘宝客放置root文件,余姚做轴承网站,网站建设电话咨询文章目录1. 题目2. 解题1. 题目
小扣当前位于魔塔游戏第一层#xff0c;共有 N 个房间#xff0c;编号为 0 ~ N-1。 每个房间的补血道具/怪物对于血量影响记于数组 nums#xff0c;其中#xff1a;
正数表示道具补血数值#xff0c;即血量增加对应数值#xff1b;负数表…
文章目录1. 题目2. 解题1. 题目
小扣当前位于魔塔游戏第一层共有 N 个房间编号为 0 ~ N-1。 每个房间的补血道具/怪物对于血量影响记于数组 nums其中
正数表示道具补血数值即血量增加对应数值负数表示怪物造成伤害值即血量减少对应数值0 表示房间对血量无影响。
小扣初始血量为 1且无上限。 假定小扣原计划按房间编号升序访问所有房间补血/打怪为保证血量始终为正值小扣需对房间访问顺序进行调整每次仅能将一个怪物房间负数的房间调整至访问顺序末尾。 请返回小扣最少需要调整几次才能顺利访问所有房间。 若调整顺序也无法访问完全部房间请返回 -1。
示例 1
输入nums [100,100,100,-250,-60,-140,-50,-50,100,150]
输出1
解释初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。示例 2
输入nums [-200,-300,400,0]
输出-1
解释调整访问顺序也无法完成全部房间的访问。提示
1 nums.length 10^5
-10^5 nums[i] 10^5来源力扣LeetCode 链接https://leetcode-cn.com/problems/p0NxJO 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
把怪兽的体力值加入优先队列并记录其总和当体力不足时把体力最大的怪兽移到末尾移到次数 1
class Solution {
public:int magicTower(vectorint nums) {long long sum accumulate(nums.begin(), nums.end(), 1LL);// long long 写的 int 报错了好多次。。。 if(sum 0) return -1; // 体力值不够不可能过关long long v 1, delta 0, ans0;priority_queueint q;for(int i 0, j; i nums.size(); i){ if(nums[i] 0){ // 怪兽加入优先队列q.push(-nums[i]);delta delta-nums[i];//记录所有怪兽的总和正值}elsev vnums[i];//自己的体力while(v-delta 0 !q.empty()){ // 当自己的体力不够打怪兽的时候把前面最大的怪兽挪到最后int tp q.top();//怪兽的攻击值q.pop();delta delta-tp;//剩余的怪兽的攻击总值ans;//移动一次}}return ans;}
};160 ms 68.8 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步