2530. Maximal Score After Applying K Operations
Approach
Max-heap; k times take max element, add to score, push ceil(max/3) back.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
A heap (priority queue) gives O(log n) insert and O(1) peek with O(log n) removal. In C#, use PriorityQueue<TElement, TPriority> (.NET 6+). Classic patterns: top-K elements (min-heap of size K), merge K sorted lists, Dijkstra's shortest path, and median in a stream (two heaps).
// Approach: Max-heap; k times take max element, add to score, push ceil(max/3) back.
// Time: O(n + k log n) Space: O(n)
public class Solution
{
public long MaxKelements(int[] nums, int k)
{
long ans = 0;
PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>();
foreach (var num in nums)
maxHeap.Enqueue(num, -num);
for (int i = 0; i < k; ++i)
{
int num = maxHeap.Dequeue();
ans += num;
maxHeap.Enqueue((num + 2) / 3, -(num + 2) / 3);
}
return ans;
}
}