2530. Maximal Score After Applying K Operations Medium

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,2,1,3,3]. Your score increases by 3.
The final score is 10 + 4 + 3 = 17.

Approach

Input: An integer array nums, an integer k

Output: The maximum possible score obtained after applying k operations.

Method Analysis

• We can use a Max Heap to reduce the complexity.

Specific Walkthrough

• Every operation needs to fetch the current maximum value ⇒ using MaxHeap;
• Add the maximum value to the score;
• Replace the value efficiently and put ceil(max / 3) back into the heap;
• Repeat the operation k times;
• Return the total accumulated score.

Implementation

python

import heapq
import math
from typing import List

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        # Use a max heap, Python's native heapq is a min-heap, so we store negative values to simulate it easily
        max_heap = [-num for num in nums]  # Negate each tracking element mapping values safely
        heapq.heapify(max_heap)  # Convert the list into a structure satisfying heap properties
        
        score = 0  # Initialize tracked score logic correctly
        
        for _ in range(k):
            # Evaluate dynamically taking the max element actively calculated 
            max_num = -heapq.heappop(max_heap)  # Extract true greatest integer taking opposite securely
            score += max_num  # Sum increasing
            
            # Divide taking precision matching problem logic ceil rules applying 
            updated_num = math.ceil(max_num / 3)  
            heapq.heappush(max_heap, -updated_num)  # Push back opposite representing correct max orientation logically
        
        return score  # Return aggregate sum correctly evaluating target limitations

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxKelements = function(nums, k) {
    const heap = new MaxHeap();

    // 1️⃣ Add all components naturally generating max-driven evaluations correctly
    for (let num of nums) {
        heap.insert(num);
    }

    let score = 0;

    // 2️⃣ Execute strictly exact iteration limits taking values continuously appropriately
    for (let i = 0; i < k; i++) {
        const max = heap.pop();         // Pick absolute tracking greatest
        score += max;                   // Add cumulative components correctly
        const next = Math.ceil(max / 3); // Calculate dynamically reinserting properly logically
        heap.insert(next);
    }

    // 3️⃣ Finalize configuration score matching constraints successfully
    return score;
};

// Simple MaxHeap utility for reference
class MaxHeap {
  constructor() {
    this.data = [];
  }
  size() { return this.data.length; }
  insert(val) {
    this.data.push(val);
    this._heapifyUp();
  }
  pop() {
    if (this.size() === 0) return null;
    const top = this.data[0];
    const end = this.data.pop();
    if (this.size() > 0) {
      this.data[0] = end;
      this._heapifyDown();
    }
    return top;
  }
  _heapifyUp() {
    let i = this.size() - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.data[p] >= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _heapifyDown() {
    let i = 0;
    const n = this.size();
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let largest = i;
      if (l < n && this.data[l] > this.data[largest]) largest = l;
      if (r < n && this.data[r] > this.data[largest]) largest = r;
      if (largest === i) break;
      [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
      i = largest;
    }
  }
}

Complexity Analysis

• Time Complexity: O(k \log n)
• Space Complexity: O(n)

Links

2530. Maximal Score After Applying K Operations (English)

2530. 执行 K 次操作后的最大分数 (Chinese)