class Solution {
public:
long long maxKelements(vector<int>& nums, int k) {
}
};
6285. 执行 K 次操作后的最大分数
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。
在一步 操作 中：
0 <= i < nums.length 的下标 i ，nums[i] ，并且nums[i] 替换为 ceil(nums[i] / 3) 。返回在 恰好 执行 k 次操作后，你可能获得的最大分数。
向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。
示例 1：
输入：nums = [10,10,10,10,10], k = 5 输出：50 解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。
示例 2：
输入：nums = [1,10,3,3,3], k = 3 输出：17 解释：可以执行下述操作： 第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。分数增加 10 。 第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。分数增加 4 。 第 3 步操作：选中 i = 2 ，nums 变为 [1,1,1,3,3] 。分数增加 3 。 最后分数是 10 + 4 + 3 = 17 。
提示：
1 <= nums.length, k <= 1051 <= nums[i] <= 109原站题解
java 解法, 执行用时: 116 ms, 内存消耗: 58.8 MB, 提交时间: 2023-10-18 17:34:08
class Solution {
public long maxKelements(int[] nums, int k) {
long ans = 0;
// 内置优先队列
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->(b-a));
for (int x : nums) pq.offer(x);
for (; k > 0; k-- ) {
int t = pq.peek();
pq.poll();
ans += (long)t;
pq.offer((t + 2) / 3);
}
return ans;
}
}
rust 解法, 执行用时: 28 ms, 内存消耗: 4.2 MB, 提交时间: 2023-10-18 17:31:52
use std::collections::BinaryHeap;
impl Solution {
pub fn max_kelements(nums: Vec<i32>, k: i32) -> i64 {
let mut h = BinaryHeap::from(nums); // 原地堆化（最大堆）
let mut ans = 0i64;
for _ in 0..k {
let mx = h.pop().unwrap();
ans += mx as i64;
h.push((mx + 2) / 3);
}
ans
}
}
java 解法, 执行用时: 31 ms, 内存消耗: 55.1 MB, 提交时间: 2023-10-18 17:23:37
class Solution {
public long maxKelements(int[] nums, int k) {
heapify(nums); // 原地堆化（最大堆）
long ans = 0;
while (k-- > 0) {
ans += nums[0]; // 堆顶
nums[0] = (nums[0] + 2) / 3;
sink(nums, 0); // 堆化（只需要把 nums[0] 下沉）
}
return ans;
}
// 原地堆化（最大堆）
// 堆化可以保证 h[0] 是堆顶元素，且 h[i] >= max(h[2*i+1], h[2*i+2])
private void heapify(int[] h) {
// 下标 >= h.length / 2 的元素是二叉树的叶子，无需下沉
// 倒着遍历，从而保证 i 的左右子树一定是堆，那么 sink(h, i) 就可以把左右子树合并成一个堆
for (int i = h.length / 2 - 1; i >= 0; i--) {
sink(h, i);
}
}
// 把 h[i] 不断下沉，直到 i 的左右儿子都 <= h[i]
private void sink(int[] h, int i) {
int n = h.length;
while (2 * i + 1 < n) {
int j = 2 * i + 1; // i 的左儿子
if (j + 1 < n && h[j + 1] > h[j]) { // i 的右儿子比 i 的左儿子大
j++;
}
if (h[j] <= h[i]) { // 说明 i 的左右儿子都 <= h[i]，停止下沉
break;
}
swap(h, i, j); // 下沉
i = j;
}
}
// 交换 h[i] 和 h[j]
private void swap(int[] h, int i, int j) {
int tmp = h[i];
h[i] = h[j];
h[j] = tmp;
}
}
cpp 解法, 执行用时: 224 ms, 内存消耗: 80.3 MB, 提交时间: 2023-01-09 10:34:03
class Solution {
public:
long long maxKelements(vector<int>& nums, int k) {
long long ans = 0;
priority_queue<long long> pq;
for (int x : nums) pq.push(x);
while (k--) {
long long t = pq.top(); pq.pop();
ans += t;
pq.push((t + 2) / 3);
}
return ans;
}
};
golang 解法, 执行用时: 156 ms, 内存消耗: 9.1 MB, 提交时间: 2023-01-09 10:33:42
func maxKelements(nums []int, k int) (ans int64) {
h := hp{nums}
heap.Init(&h)
for ; k > 0; k-- {
ans += int64(h.IntSlice[0])
h.IntSlice[0] = (h.IntSlice[0] + 2) / 3
heap.Fix(&h, 0)
}
return
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (hp) Push(interface{}) {}
func (hp) Pop() (_ interface{}) { return }
python3 解法, 执行用时: 284 ms, 内存消耗: 26.4 MB, 提交时间: 2023-01-09 10:33:08
# 用一个最大堆模拟，每次循环累加堆顶，同时修改堆顶。
class Solution:
def maxKelements(self, nums: List[int], k: int) -> int:
from heapq import heapreplace, heapify
for i in range(len(nums)):
nums[i] = -nums[i] # 最大堆
heapify(nums)
ans = 0
for _ in range(k):
ans -= heapreplace(nums, nums[0] // 3)
return ans