建站宝盒如何使用,纪念馆展厅设计,企业网站建设公司价格,wordpress 多语言版LCP 30. 魔塔游戏
难度: 中等
题目: 小扣当前位于魔塔游戏第一层#xff0c;共有 N 个房间#xff0c;编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums#xff0c;其中正数表示道具补血数值#xff0c;即血量增加对应数值#xff1b;负数表示怪物造…LCP 30. 魔塔游戏
难度: 中等
题目: 小扣当前位于魔塔游戏第一层共有 N 个房间编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums其中正数表示道具补血数值即血量增加对应数值负数表示怪物造成伤害值即血量减少对应数值0 表示房间对血量无影响。 小扣初始血量为 1且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪为保证血量始终为正值小扣需对房间访问顺序进行调整每次仅能将一个怪物房间负数的房间调整至访问顺序末尾。请返回小扣最少需要调整几次才能顺利访问所有房间。若调整顺序也无法访问完全部房间请返回 -1。 提示 1 nums.length 10^5-10^5 nums[i] 10^5 示例 1 输入nums [100,100,100,-250,-60,-140,-50,-50,100,150] 输出1 解释初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。 分析
如果全部和加起来是小于等于0的那么不管怎么排都是不能访问到所有房间的所以我们可以首先求一下全部的和注意要开long long大于0的话就是一定有解的因为最坏情况我们可以将所有的负数调整到 最后这样就一定可以全部访问完那么怎么来求最少要交换多少次呢如果当前的血量是负数我们就肯定需要将怪物往后挪挪哪个怪物呢因为要挪动次数最少所以我们考虑挪动前面最厉害的怪物也就是nums[]最小的可以证明这样做是最优的依次这样访问就可以了那么怎么快速得到最小的nums[]呢我们可以用堆数据结构是小根堆,cpp可以使用priority_queueint, vectorint, greaterint, 这样我们就可以在logn的时间获得最小值总体时间复杂度是nlogn因为每个元素最多就是进入小根堆1一次
优先队列 贪心
class Solution {
public:using LL long long;int magicTower(vectorint nums) {LL sum accumulate(nums.begin(), nums.end(), 1ll);if (sum 0) return -1;int n nums.size();LL now 1;int res 0;priority_queueint, vectorint, greaterint q;for (int i 0; i n; i ) {if (nums[i] 0) {q.push(nums[i]);}now nums[i];if (now 0) {res ;now - q.top();q.pop();}}return res;}
};时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
结束了
