class Solution {
public:
int magicTower(vector<int>& nums) {
}
};
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原站题解
php 解法, 执行用时: 229 ms, 内存消耗: 27.5 MB, 提交时间: 2024-02-06 09:28:27
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function magicTower($nums) {
$n = count($nums);
$cur_sum = 0; #当前和
$time = 0; #把负数往后扔的次数
$minSum = 0; #负数的abs值
$minHeap = new SplMinHeap(); #最小堆。每次把最小的负数，扔到后面去
for ( $i = 0; $i < $n; $i ++ ) {
$cur_sum += $nums[$i]; #当前和
if ( $nums[$i] < 0 ) { #所有的负数，都进堆
$minHeap->insert($nums[$i]);
}
if ( $cur_sum < 0 ) { #当前卡住了。需要把前面经历过的这些负数中，扔一个最小的到后面
$cur_min = $minHeap->extract();
$minSum -= $cur_min; #这些扔到后面的，眼前跳过了，在最后还是要掉血
$cur_sum -= $cur_min; #扔掉这个最小的负数。cur_sum会变大
$time += 1; #记录往后扔的次数
}
}
if ( $cur_sum < $minSum ) { #如果正值，不能够把扔到末尾的负值抵消掉
return -1;
}
return $time;
}
}
golang 解法, 执行用时: 112 ms, 内存消耗: 9 MB, 提交时间: 2023-09-26 20:25:07
func magicTower(nums []int) int {
sum ,rem , res := 1 , 0 , 0 //sum当前血量，rem是被换到最后的房间的怪物伤害，res为结果
h := new(IntHeap)
for i:=0;i<len(nums);i++{
if nums[i] < 0{ //如果当前房间有怪就加入堆中
heap.Push(h,nums[i])
}
sum += nums[i]
for sum <= 0{ //如果当前血量小于等于0了，把遇到的怪中伤害最高的移到最后去
if len(*h) != 0{
res++
temp := heap.Pop(h).(int)
sum -= temp
rem -= temp //记录移到后面的怪的伤害
}else {
return -1 //如果堆为空了sum还是小于等于0，就失败了
}
}
}
if sum - rem > 0{ //达到原先的最后一个房间后，再看之前被换到后面的怪物
return res
}else{
return -1
}
}
type IntHeap []int
func (h IntHeap)Len()int {
return len(h)
}
func (h IntHeap)Less(i, j int)bool {
return h[i] < h[j]
}
func (h IntHeap)Swap(i, j int){
h[i] , h[j] = h[j] , h[i]
}
func (h *IntHeap)Push(x interface{}){
*h = append(*h , x.(int))
}
func (h *IntHeap)Pop() interface{}{
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
python3 解法, 执行用时: 100 ms, 内存消耗: 30.2 MB, 提交时间: 2023-09-26 20:24:26
import heapq
class Solution:
def magicTower(self, nums: List[int]) -> int:
if sum(nums) < 0:
return -1
hurts = []
blood = 0
counts = 0
heapq.heapify(hurts)
for i in nums:
blood += i
if i < 0:
heapq.heappush(hurts, i)
if blood < 0:
counts += 1
blood -= heapq.heappop(hurts)
return counts
python3 解法, 执行用时: 132 ms, 内存消耗: 30.5 MB, 提交时间: 2023-09-26 20:23:34
class Solution:
def magicTower(self, nums: List[int]) -> int:
n = len(nums)
cur_sum = 0 #当前和
time = 0 #把负数往后扔的次数
minSum = 0 #负数的abs值
minHeap = [] #最小堆。每次把最小的负数，扔到后面去
for i in range(n):
cur_sum += nums[i] #当前和
if nums[i] < 0: #所有的负数，都进堆
heapq.heappush(minHeap, nums[i])
if cur_sum < 0: #当前卡住了。需要把前面经历过的这些负数中，扔一个最小的到后面
cur_min = heapq.heappop(minHeap)
minSum -= cur_min #这些扔到后面的，眼前跳过了，在最后还是要掉血
cur_sum -= cur_min #扔掉这个最小的负数。cur_sum会变大
time += 1 #记录往后扔的次数
if cur_sum < minSum: #如果正值，不能够把扔到末尾的负值抵消掉
return -1
return time
cpp 解法, 执行用时: 104 ms, 内存消耗: 69.2 MB, 提交时间: 2023-09-26 20:22:49
class Solution {
using ll = long long;
public:
int magicTower(vector<int>& a) {
priority_queue<int> q;
ll sum = 1; // 总和，用于特判 -1 的情况
for(int x : a) {
sum += x;
}
if(sum <= 0) return -1;
ll blood = 1, ret = 0;
for(int x : a) {
if(x < 0) q.push(-x); // 默认最大的排在前面，所以我们取负值（绝对值最大的负数）
blood += x;
while(blood <= 0) {
int cur = q.top();
q.pop();
blood += cur; // 由于提前取了绝对值，所以加上该“已经被消耗的”血量即可
ret++; // 调整一次
}
}
return ret;
}
};
java 解法, 执行用时: 11 ms, 内存消耗: 57.4 MB, 提交时间: 2023-09-26 20:22:31
class Solution {
public int magicTower(int[] nums) {
int sum = 0;
for(int i : nums) sum += i;
if(sum < 0) return -1;
int res = 0;
long health = 1;
Queue<Integer> min = new PriorityQueue();
for(int i = 0; i < nums.length; i++){
if(nums[i] < 0) min.offer(nums[i]);
health += nums[i];
if(health > 0) continue;
health -= min.poll();
res++;
}
return res;
}
}
java 解法, 执行用时: 9 ms, 内存消耗: 57.1 MB, 提交时间: 2023-09-26 20:22:17
class Solution {
public int magicTower(int[] nums) {
int sum = 1;
for(int i = 0 ; i < nums.length ; i ++){
sum += nums[i];
}
if(sum <= 0) return -1; //算出所有回合后的血量是否为正数
//开始模拟
long blood = 1;
PriorityQueue<Integer> pq = new PriorityQueue<>();
int last = 0;
for(int i = 0 ; i < nums.length ; i ++){
if(nums[i] < 0){
pq.offer(nums[i]);
if(blood + nums[i] <= 0){ //这回合过后就要死了，需要把前面扣最多的血移到最后去
last ++; //记录移动的次数
blood -= pq.poll(); //加回之前扣除最多的血量
}
}
blood += nums[i];
}
return last;
}
}