2530. Maximal Score After Applying K Operations
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 that0 <= i < nums.length
, - increase your score by
nums[i]
, and - replace
nums[i]
withceil(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,2,1,3,3]. Your score increases by 3. The final score is 10 + 4 + 3 = 17.
Constraints:
1 <= nums.length, k <= 105
1 <= 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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 |