[LeetCode] 2558. Take Gifts From the Richest Pile

https://leetcode.com/problems/take-gifts-from-the-richest-pile/description/

leetcode - Take Gifts From the Richest Pile

문제 유형: 우선순위 큐

문제 난이도: Easy

 

문제

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

• Choose the pile with the maximum number of gifts.
• If there is more than one pile with the maximum number of gifts, choose any.
• Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

 

1초마다 당신은 가장 큰 수를 하나 골라서 루트를 취하고 소수점 부분을 버리는 연산을 해야합니다.

k초이후의 배열의 요소들의 합을 구하시오.

풀이

최대 힙 우선순위 큐에 다 담고, k번동안 가장 큰 수를 꺼내서 루트를 취해서 floor를 해주고 다시 넣으면 된다.

그 뒤 모든 요소를 다 더해주면 된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        int n = gifts.size();
        priority_queue<int> maxHeap;
        for(const auto &gift : gifts) maxHeap.push(gift);

        while(k--) {
            int t = maxHeap.top();
            maxHeap.pop();
            maxHeap.push(sqrt(t));
        }

        long long ans = 0;
        while(!maxHeap.empty()) {
            ans += maxHeap.top();
            maxHeap.pop();
        }

        return ans;
    }
};