Take Gifts From the Richest Pile

Leetcode Problem:

• Take Gifts From the Richest Pile

Summary

• The problem requires to find the number of gifts remaining after k seconds, where each second, the maximum pile is chosen and its size is reduced to the floor of its square root.

Approach

• A heap data structure is used to store the number of gifts in each pile
• The pop operation is used to choose the maximum pile and reduce its size to the floor of its square root
• The process is repeated for k seconds.

Complexity

• O(n log n) due to the heap operations, where n is the number of piles.

Explanation

• The provided solution code first initializes a heap with the number of gifts in each pile
• Then, it enters a loop that runs for k seconds
• In each iteration, it pops the maximum pile from the heap, reduces its size to the floor of its square root, and pushes it back into the heap
• Finally, it calculates the total number of gifts remaining by summing up the sizes of all piles in the heap.

Solution Code:

struct _heap{
    int arr[1002];
    int size;
    _heap(){
        size = 1;
    }
    void push(int a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx] > arr[idx/2]){
            int t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx/=2;
        }
    }
    int pop(){
        int ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j>= size) break;
            if(j+1 < size && arr[j] < arr[j+1]){
                j++;
            }
            if(arr[i] < arr[j]){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else {
                break;
            }
        }


        return ret;
    }
};

class Solution {
public:
    _heap h;
    long long pickGifts(vector& gifts, int k) {
        for(int i = 0 ; i < gifts.size(); i++){
            h.push(gifts[i]);
        }
        while(k--){
            int gift = h.pop();
            int i = 1;
            while(i*i <= gift) i++;
            i--;
            h.push(i);
        }
        long long sum = 0;
        for(int i = 1; i < h.size; i++){
            sum += h.arr[i];
        }
        return sum;
    }
};