diff options
Diffstat (limited to 'maximal_score_apply_k_operation.py')
-rw-r--r-- | maximal_score_apply_k_operation.py | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/maximal_score_apply_k_operation.py b/maximal_score_apply_k_operation.py new file mode 100644 index 0000000..67f1ce1 --- /dev/null +++ b/maximal_score_apply_k_operation.py @@ -0,0 +1,36 @@ +# 2530. Maximal Score After Applying K Operations +import heapq +from math import ceil + +""" +you are given a 0-indexed integer array 'nums' and an integer 'k'. you have a +starting score of 0. in one operation you can 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'. +""" + + +class Solution(object): + def maxKelements(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + pq = [-n for n in nums] + heapq.heapify(pq) + score = 0 + while k > 0: + element = -heapq.heappop(pq) + score += element + heapq.heappush(pq, -ceil(element / 3)) + k -= 1 + return score + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxKelements(nums=[10, 10, 10, 10, 10], k=5)) + print(obj.maxKelements(nums=[1, 10, 3, 3, 3], k=3)) |