中山精品网站建设新闻,网络营销的实现方式包括,wordpress企业模板免费下载,电商网站开发 文献综述文章目录 题目描述问题分析程序代码 题目描述 原题链接 小扣当前位于魔塔游戏第一层#xff0c;共有 N 个房间#xff0c;编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums#xff0c;其中正数表示道具补血数值#xff0c;即血量增加对应数值#xff1b… 文章目录 题目描述问题分析程序代码 题目描述 原题链接 小扣当前位于魔塔游戏第一层共有 N 个房间编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums其中正数表示道具补血数值即血量增加对应数值负数表示怪物造成伤害值即血量减少对应数值0 表示房间对血量无影响。
小扣初始血量为 1且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪为保证血量始终为正值小扣需对房间访问顺序进行调整每次仅能将一个怪物房间负数的房间调整至访问顺序末尾。请返回小扣最少需要调整几次才能顺利访问所有房间。若调整顺序也无法访问完全部房间请返回 -1。
问题分析
当访问到第 i 个房间当前的血量值不为正数说明需要将一个怪物房间负数的房间调整至访问顺序末尾。
而为了确保调整次数最少则需要用一个小顶堆维护当前数值最小的怪物房间并将其调整至顺序末尾。
程序代码
class Solution {
public:int magicTower(vectorint nums) {priority_queueint, vectorint, greaterint q;int cnt 0;long long sum 1, t 0;for(auto num : nums) {if(num 0) q.push(num);sum num;if( sum 0 ) {cnt;t q.top();sum - q.top();q.pop();}}sum t;return sum 0 ? -1 : cnt;}
};
