> ## Content Index
> Fetch the complete content index at: https://blog.anthea.day/llms.txt
> Use this file to discover other available public pages before exploring further.

# LeetCode 2530. Maximal Score After Applying K Operations
- URL: https://blog.anthea.day/leetcode-c-e5-88-b7-e9-a1-8c-e7-ad-86-e8-a8-98-11/
- Published: 2023-01-08T04:59:31.000Z
- Updated: 2026-11-07T18:26:17.000Z
- Author: Anthea / 芫荽
- Tags: #Migrated-1792241843742, #Import 2026-10-17 12:57, Coding, LeetCode 刷題筆記

> 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:**

```vbnet
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:**

```vbnet
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 ，控制總共要遍歷幾次。

```csharp
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](https://blog.csdn.net/sigmarising/article/details/114625754?ref=blog.anthea.day) 之後才有的型別，使用時要注意一下。

根據[官方的文件](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2?view=net-7.0&ref=blog.anthea.day)說明，PriorityQueue 的 Pop 是取 Priority 中最小的那一個出來，也就是說，假設我們按照這樣的順序建立了一個 PriorityQueue：

```csharp
// 建立一個新的 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 應該會是最小的，在這裡我們可以把它變成負數來達到目的：

```javascript
// 以 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 就可以順利拿出最大的值。完整的程式碼如下：

```csharp
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

---

#### 參考資料

- [官方文件](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2?view=net-7.0&ref=blog.anthea.day)
- [C# 中的優先隊列（Priority Queue）](https://blog.csdn.net/sigmarising/article/details/114625754?ref=blog.anthea.day)
- [AntonRaichuk Submission Detail](https://leetcode.com/contest/weekly-contest-327/submissions/detail/873707982/?ref=blog.anthea.day)