526互联

[LeetCode] 2530. Maximal Score After Applying K Operations

发布时间 2023-10-18 09:55:05作者: CNoodle

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation:

  1. choose an index i such that 0 <= i < nums.length,
  2. increase your score by nums[i], and
  3. 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 <= 105
  • 1 <= nums[i] <= 109

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

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。

在一步 操作 中：

  1. 选出一个满足 0 <= i < nums.length 的下标 i ，
  2. 将你的 分数 增加 nums[i] ，并且
  3. 将 nums[i] 替换为 ceil(nums[i] / 3) 。

返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

思路是贪心，具体做法会用到一个最大堆。可以将 input 数组里的所有元素都放入最大堆，然后每次弹出堆顶元素 top，将这个元素的值累加到结果 res，然后再把这个元素执行一下操作三，再放回最大堆，如此一套流程执行 K 次之后停止。

时间O(nlogn) - 也可以是O(nlogk)，取决于你怎么创建这个最大堆

空间O(n) - 也可以是O(k)，取决于你怎么创建这个最大堆

Java实现

 1 class Solution {
 2     public long maxKelements(int[] nums, int k) {
 3         PriorityQueue<Double> queue = new PriorityQueue<>((a, b) -> Double.compare(b, a));
 4         for (int num : nums) {
 5             queue.offer((double) num);
 6         }
 7 
 8         long res = 0;
 9         while (!queue.isEmpty() && k > 0) {
10             double top = queue.poll();
11             res += top;
12             top = Math.ceil(top / 3);
13             queue.offer(top);
14             k--;
15         }
16         return res;
17     }
18 }

 

LeetCode 题目总结