Maximal Score After Applying K Operations

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<long long> pq(nums.begin(), nums.end());
        long long score = 0;
        while (k--) {
            long long x = pq.top(); pq.pop();
            score += x;
            pq.push((x + 2) / 3); // ceiling division
        }
        return score;
    }
};

import "container/heap"

type maxIntHeap []int

func (h maxIntHeap) Len() int            { return len(h) }
func (h maxIntHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h maxIntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *maxIntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *maxIntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func maxKelements(nums []int, k int) int64 {
    h := make(maxIntHeap, len(nums))
    copy(h, nums)
    heap.Init(&h)
    var score int64
    for ; k > 0; k-- {
        x := heap.Pop(&h).(int)
        score += int64(x)
        heap.Push(&h, (x+2)/3)
    }
    return score
}

import heapq
from typing import List

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        h = [-x for x in nums]
        heapq.heapify(h)
        score = 0
        for _ in range(k):
            x = -heapq.heappop(h)
            score += x
            heapq.heappush(h, -((x + 2) // 3))
        return score

class MaxHeap {
    constructor(arr = []) {
        this.heap = arr.slice();
        for (let i = (this.heap.length >> 1) - 1; i >= 0; i--) this._down(i);
    }
    size() { return this.heap.length; }
    peek() { return this.heap[0]; }
    push(v) { this.heap.push(v); this._up(this.heap.length - 1); }
    pop() {
        const top = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length) { this.heap[0] = last; this._down(0); }
        return top;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.heap[p] < this.heap[i]) { [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.heap.length;
        while (true) {
            const l = i * 2 + 1, r = l + 1;
            let b = i;
            if (l < n && this.heap[l] > this.heap[b]) b = l;
            if (r < n && this.heap[r] > this.heap[b]) b = r;
            if (b === i) break;
            [this.heap[b], this.heap[i]] = [this.heap[i], this.heap[b]];
            i = b;
        }
    }
}

function maxKelements(nums, k) {
    const pq = new MaxHeap(nums);
    let score = 0;
    while (k--) {
        const x = pq.pop();
        score += x;
        pq.push(Math.ceil(x / 3));
    }
    return score;
}

class Solution {
    public long maxKelements(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int v : nums) pq.offer(v);
        long score = 0;
        while (k-- > 0) {
            int x = pq.poll();
            score += x;
            pq.offer((x + 2) / 3);
        }
        return score;
    }
}

class MaxHeap {
    private heap: number[];

    constructor(arr: number[] = []) {
        this.heap = arr.slice();
        for (let i = (this.heap.length >> 1) - 1; i >= 0; i--) this._down(i);
    }
    size(): number { return this.heap.length; }
    peek(): number { return this.heap[0]; }
    push(v: number): void { this.heap.push(v); this._up(this.heap.length - 1); }
    pop(): number {
        const top = this.heap[0];
        const last = this.heap.pop()!;
        if (this.heap.length) { this.heap[0] = last; this._down(0); }
        return top;
    }
    private _up(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.heap[p] < this.heap[i]) { [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]]; i = p; }
            else break;
        }
    }
    private _down(i: number): void {
        const n = this.heap.length;
        while (true) {
            const l = i * 2 + 1, r = l + 1;
            let b = i;
            if (l < n && this.heap[l] > this.heap[b]) b = l;
            if (r < n && this.heap[r] > this.heap[b]) b = r;
            if (b === i) break;
            [this.heap[b], this.heap[i]] = [this.heap[i], this.heap[b]];
            i = b;
        }
    }
}

function maxKelements(nums: number[], k: number): number {
    const pq = new MaxHeap(nums);
    let score = 0;
    while (k--) {
        const x = pq.pop();
        score += x;
        pq.push(Math.ceil(x / 3));
    }
    return score;
}