Skip to content
Coding

LeetCode 2530. Maximal Score After Applying K Operations

By Anthea / 芫荽 3 min read
LeetCode 2530. Maximal Score After Applying K Operations
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 <= 10^5
  • 1 <= nums[i] <= 10^9

題解

Weekly Contest 327，Medium。

簡單來說要從給定的 nums 得到一個最大的合，可以選擇 k 個數字，每次挑出來一個數字之後，要把挑出來的數字 nums[i] / 3 ，取無條件進位塞回去 nums。

暴力解

跑兩個迴圈，第一個是 nums ，遍歷完之後找出最大的，加完之後除以 3 再放回去；第二個迴圈是 k ，控制總共要遍歷幾次。

public long MaxKelements(int[] nums, int k) { 
    long sum = 0; 
     
    while(k > 0) 
    { 
        long max = -1; 
        var maxIndex = -1; 
 
        for (var index = 0; index < nums.Length; index++) 
        { 
            var curent = nums[index]; 
            if (curent > max) 
            { 
                max = Convert.ToInt64(curent); 
                maxIndex = index; 
            } 
        } 
         
        sum += max; 
        nums[maxIndex] = Convert.ToInt32(Math.Ceiling((double)nums[maxIndex] / 3)); 
        k--; 
    } 
     
    return sum; 
}

效能

  • Time complexity: O(n * m)
  • Space complexity: O(1)
  • Time Limit Exceeded

PriorityQueue

參考其他人的答案後學到的新東西：有排序的 Queue。這個是 C#10 之後才有的型別，使用時要注意一下。

根據官方的文件說明，PriorityQueue 的 Pop 是取 Priority 中最小的那一個出來，也就是說，假設我們按照這樣的順序建立了一個 PriorityQueue：

// 建立一個新的 PriorityQueue 
// PriorityQueue<int, TPriority> 
// 第一個 int 是 Element 型別 
// 第二個 int 是 Priority 的型別 
var queue = new PriorityQueue<int, int>(); 
 
// 以 Example2 為例 
// nums = [1,10,3,3,3] 
foreach(var num in nums) 
{ 
    // PriorityQueue 的 Push 是 Enqueue 
    queue.Enqueue(num, num); 
} 
 
// queue.Enqueue(1, 1); 
// queue.Enqueue(10, 10); 
// queue.Enqueue(3, 3); 
// queue.Enqueue(3, 3); 
// queue.Enqueue(3, 3);

這時候 Pop 拿最後一個出來，應該會拿到 1。但我們想要的是拿到最大的數值，所以最大的數字，他的 Priority 應該會是最小的，在這裡我們可以把它變成負數來達到目的：

// 以 Example2 為例 
// nums = [1,10,3,3,3] 
foreach(var num in nums) 
{ 
    queue.Enqueue(num, 0 - num); 
} 
 
// queue.Enqueue(1, -1); 
// queue.Enqueue(10, -10); 
// queue.Enqueue(3, -3); 
// queue.Enqueue(3, -3); 
// queue.Enqueue(3, -3);

這樣 10 的 Priority 就變成了最小的 -10，使用 Pop 就可以順利拿出最大的值。完整的程式碼如下：

var queue = new PriorityQueue<int, int>(); 
foreach(var num in nums) 
{ 
    queue.Enqueue(num, 0 - num); 
} 
 
long sum = 0; 
while(k > 0) 
{ 
    // PriorityQueue 的 Pop 是 Dequeue 
    var max = queue.Dequeue(); 
    sum += max; 
 
    var x = (int) Math.Ceiling((double)max / 3); 
    queue.Enqueue(x, 0 - x); 
     
    k--; 
} 
 
return sum;

效能

  • Time complexity: O(n)
  • Space complexity: O(n)
  • Runtime: 302 ms
  • Memory: 51.8 MB

參考資料