本文主要是介绍LCP 30. 魔塔游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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_queue<int, vector<int>, greater<int>>
, 这样我们就可以在logn
的时间获得最小值,总体时间复杂度是nlogn
因为每个元素最多就是进入小根堆1一次
优先队列 + 贪心
class Solution {
public:using LL = long long;int magicTower(vector<int>& 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_queue<int, vector<int>, greater<int>> 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)
结束了
这篇关于LCP 30. 魔塔游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!