2530.执行K次操作后的最大分数

链接：2530.执行K次操作后的最大分数
难度：Medium
标签：贪心、数组、堆（优先队列）
简介：给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

题解 1 - cpp

• 编辑时间：2023-01-08
• 执行用时：160ms
• 内存消耗：70.8MB
• 编程语言：cpp
• 解法介绍：堆。

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        priority_queue<int> q;
        long long ans = 0;
        int idx = nums.size() - 1;
        while (k--) {
            if (q.size() && (idx < 0 || q.top() >= nums[idx])) {
                int num = q.top();
                q.pop();
                ans += num;
                q.push(ceil(1.0 * num / 3));
            } else {
                int num = nums[idx--];
                ans += num;
                q.push(ceil(1.0 * num / 3));
            }
        }
        return ans;
    }
};

题解 2 - rust

• 编辑时间：2023-01-08
• 执行用时：36ms
• 内存消耗：4.6MB
• 编程语言：rust
• 解法介绍：同上。

use std::collections::BinaryHeap;
impl Solution {
    pub fn max_kelements(nums: Vec<i32>, k: i32) -> i64 {
        let mut k = k;
        let mut heap = BinaryHeap::new();
        for num in nums {
            heap.push(num);
        }
        let mut ans: i64 = 0;
        while k != 0 {
            let num = heap.pop().unwrap() as i64;
            ans += num;
            let num = (num as f64 / 3.0).ceil() as i32;
            heap.push(num);
            k -= 1;
        }
        ans
    }
}

题解 3 - python

• 编辑时间：2023-10-18
• 执行用时：1604ms
• 内存消耗：44.59MB
• 编程语言：python
• 解法介绍：堆存储。

class Node:
        def __init__(self, val):
            self.val = val
        def __lt__(self, o):
            return o.val < self.val
    
    class Solution:
        def maxKelements(self, nums: List[int], k: int) -> int:
            q = [Node(num) for num in nums]
            heapify(q)
            res = 0
            while k:
                res += q[0].val
                heappush(q, Node(ceil(heappop(q).val / 3)))
                k -= 1
            return res
    

题解 4 - python

• 编辑时间：2023-10-18
• 执行用时：344ms
• 内存消耗：29.59MB
• 编程语言：python
• 解法介绍：堆存储。

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        for i in range(len(nums)): nums[i] *= -1
        heapify(nums)
        res = 0
        for _ in range(k):
            res += -nums[0]
            heappush(nums, -ceil(heappop(nums) / -3))
        return res