秦皇岛的网站建设公司,电脑网站微信支付怎么做的,收费的网站怎么做的,郑州做企业网站的目录 LCP 30. 魔塔游戏
题目描述#xff1a;
实现代码与解析#xff1a;
贪心
原理思路#xff1a; LCP 30. 魔塔游戏
题目描述#xff1a; 小扣当前位于魔塔游戏第一层#xff0c;共有 N 个房间#xff0c;编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于…目录 LCP 30. 魔塔游戏
题目描述
实现代码与解析
贪心
原理思路 LCP 30. 魔塔游戏
题目描述 小扣当前位于魔塔游戏第一层共有 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
实现代码与解析
贪心
class Solution {public int magicTower(int[] nums) {int n nums.length;PriorityQueueInteger q new PriorityQueue();int res 0; long hp 1; // 当前血量long d 0; // 转移到后面的总和最后还要加上for (int i 0; i n; i) {if (nums[i] 0) q.offer(nums[i]);hp nums[i];if (hp 1) { // 血量不够反悔把损失最大血量的关卡像后移动res; int t q.peek();q.poll();hp - t; d t;}}hp d;return hp 0 ? res : -1;}
}
原理思路 利用遍历数组把当前数小于0的放入小根堆挑战当前怪物若hp1说明需要反悔把前面挑战怪物掉血最多的放在最后利用d记录下来所以返回的怪物在遍历完成后加上最后血量大于0说明有可行的调整方法返回若小于等于0返回-1。 至于为什么反悔只用反悔一次因为我们是先挑战怪物若失败才进行反悔优先级队列中最小的值都一定比此层加入的值小或者等于只反悔一次就可以让hp变成正的。
