Description#
You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.
In one operation:
- choose an index
i such that 0 <= i < nums.length, - increase your score by
nums[i], and - replace
nums[i] with ceil(nums[i] / 3).
Return the maximum possible score you can attain after applying exactly k operations.
The ceiling function ceil(val) is the least integer greater than or equal to val.
Example 1:
Input: nums = [10,10,10,10,10], k = 5
Output: 50
Explanation: Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.
Example 2:
Input: nums = [1,10,3,3,3], k = 3
Output: 17
Explanation: You can do the following operations:
Operation 1: Select i = 1, so nums becomes [1,4,3,3,3]. Your score increases by 10.
Operation 2: Select i = 1, so nums becomes [1,2,3,3,3]. Your score increases by 4.
Operation 3: Select i = 2, so nums becomes [1,1,1,3,3]. Your score increases by 3.
The final score is 10 + 4 + 3 = 17.
Constraints:
1 <= nums.length, k <= 1051 <= nums[i] <= 109
Solutions#
Solution 1: Priority Queue (Max Heap)#
To maximize the sum of scores, we need to select the element with the maximum value at each step. Therefore, we can use a priority queue (max heap) to maintain the element with the maximum value.
At each step, we take out the element with the maximum value $v$ from the priority queue, add $v$ to the answer, and replace $v$ with $\lceil \frac{v}{3} \rceil$, and then add it to the priority queue. After repeating this process $k$ times, we return the answer.
The time complexity is $O(n + k \times \log n)$, and the space complexity is $O(n)$ or $O(1)$. Here, $n$ is the length of the array $nums$.
1
2
3
4
5
6
7
8
9
10
| class Solution:
def maxKelements(self, nums: List[int], k: int) -> int:
h = [-v for v in nums]
heapify(h)
ans = 0
for _ in range(k):
v = -heappop(h)
ans += v
heappush(h, -(ceil(v / 3)))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public long maxKelements(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int v : nums) {
pq.offer(v);
}
long ans = 0;
while (k-- > 0) {
int v = pq.poll();
ans += v;
pq.offer((v + 2) / 3);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
long long maxKelements(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());
long long ans = 0;
while (k--) {
int v = pq.top();
pq.pop();
ans += v;
pq.push((v + 2) / 3);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func maxKelements(nums []int, k int) (ans int64) {
h := &hp{nums}
heap.Init(h)
for ; k > 0; k-- {
v := h.pop()
ans += int64(v)
h.push((v + 2) / 3)
}
return
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int { return heap.Pop(h).(int) }
|
1
2
3
4
5
6
7
8
9
10
11
12
| function maxKelements(nums: number[], k: number): number {
const pq = new MaxPriorityQueue();
nums.forEach(num => pq.enqueue(num));
let ans = 0;
while (k > 0) {
const v = pq.dequeue()!.element;
ans += v;
pq.enqueue(Math.floor((v + 2) / 3));
k--;
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| use std::collections::BinaryHeap;
impl Solution {
pub fn max_kelements(nums: Vec<i32>, k: i32) -> i64 {
let mut pq = BinaryHeap::from(nums);
let mut ans = 0;
let mut k = k;
while k > 0 {
if let Some(v) = pq.pop() {
ans += v as i64;
pq.push((v + 2) / 3);
k -= 1;
}
}
ans
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
| class Solution:
def maxKelements(self, nums: List[int], k: int) -> int:
for i, v in enumerate(nums):
nums[i] = -v
heapify(nums)
ans = 0
for _ in range(k):
ans -= heapreplace(nums, -ceil(-nums[0] / 3))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
long long maxKelements(vector<int>& nums, int k) {
make_heap(nums.begin(), nums.end());
long long ans = 0;
while (k--) {
int v = nums[0];
ans += v;
pop_heap(nums.begin(), nums.end());
nums.back() = (v + 2) / 3;
push_heap(nums.begin(), nums.end());
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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(any) {}
func (hp) Pop() (_ any) { return }
|
