{"id":9923,"date":"2023-02-04T21:12:41","date_gmt":"2023-02-05T05:12:41","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9923"},"modified":"2023-02-04T21:15:09","modified_gmt":"2023-02-05T05:15:09","slug":"leetcode-2558-take-gifts-from-the-richest-pile","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/heap\/leetcode-2558-take-gifts-from-the-richest-pile\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2558.\u00a0Take Gifts From the Richest Pile"},"content":{"rendered":"\n<p>You are given an integer array&nbsp;<code>gifts<\/code>&nbsp;denoting the number of gifts in various piles. Every second, you do the following:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Choose the pile with the maximum number of gifts.<\/li><li>If there is more than one pile with the maximum number of gifts, choose any.<\/li><li>Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the number of gifts remaining after&nbsp;<\/em><code>k<\/code><em>&nbsp;seconds.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> gifts = [25,64,9,4,100], k = 4\n<strong>Output:<\/strong> 29\n<strong>Explanation:<\/strong> \nThe gifts are taken in the following way:\n- In the first second, the last pile is chosen and 10 gifts are left behind.\n- Then the second pile is chosen and 8 gifts are left behind.\n- After that the first pile is chosen and 5 gifts are left behind.\n- Finally, the last pile is chosen again and 3 gifts are left behind.\nThe final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> gifts = [1,1,1,1], k = 4\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> \nIn this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. \nThat is, you can't take any pile with you. \nSo, the total gifts remaining are 4.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= gifts.length &lt;= 10<sup>3<\/sup><\/code><\/li><li><code>1 &lt;= gifts[i] &lt;= 10<sup>9<\/sup><\/code><\/li><li><code>1 &lt;= k &lt;= 10<sup>3<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Priority Queue<\/strong><\/h2>\n\n\n\n<p>Keep all numbers in a priority queue (max heap), each time extract the top one (largest one), then put num  &#8211; sqrt(num) back to the queue.<\/p>\n\n\n\n<p>Tip: We can early return if all the numbers become 1.<\/p>\n\n\n\n<p>Time complexity: O(n + klogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  long long pickGifts(vector<int>& gifts, int k) {\n    long long ans = accumulate(begin(gifts), end(gifts), 0LL);\n    priority_queue<int> q(begin(gifts), end(gifts));\n    while (k-- && q.top() > 1) {\n      int cur = q.top(); q.pop();\n      int next = sqrt(cur);\n      ans -= (cur - next);\n      q.push(next);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;gifts&nbsp;denoting the number of gifts in various piles. Every second, you do the following: Choose the pile with the maximum&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71],"tags":[222,790,72],"class_list":["post-9923","post","type-post","status-publish","format-standard","hentry","category-heap","tag-easy","tag-max-heap","tag-priority-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9923","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9923"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9923\/revisions"}],"predecessor-version":[{"id":9928,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9923\/revisions\/9928"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9923"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9923"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9923"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}