{"id":7297,"date":"2020-08-23T11:05:16","date_gmt":"2020-08-23T18:05:16","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7297"},"modified":"2020-09-14T22:23:58","modified_gmt":"2020-09-15T05:23:58","slug":"leetcode-1561-maximum-number-of-coins-you-can-get","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1561-maximum-number-of-coins-you-can-get\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1561. Maximum Number of Coins You Can Get"},"content":{"rendered":"\n<p>There are 3n&nbsp;piles of coins of&nbsp;varying size, you and your friends will take piles of coins as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>In each step, you will choose&nbsp;<strong>any&nbsp;<\/strong>3 piles of coins (not necessarily consecutive).<\/li><li>Of your choice,&nbsp;Alice&nbsp;will pick&nbsp;the pile with the maximum number of coins.<\/li><li>You will pick the next pile with maximum number of coins.<\/li><li>Your friend Bob will pick the last pile.<\/li><li>Repeat&nbsp;until&nbsp;there are no more piles of coins.<\/li><\/ul>\n\n\n\n<p>Given an array of integers&nbsp;<code>piles<\/code>&nbsp;where&nbsp;<code>piles[i]<\/code>&nbsp;is the number of coins in the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;pile.<\/p>\n\n\n\n<p>Return the maximum number of coins which you can have.<\/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> piles = [2,4,1,2,7,8]\n<strong>Output:<\/strong> 9\n<strong>Explanation: <\/strong>Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with <strong>7<\/strong> coins and Bob the last one.\nChoose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with <strong>2<\/strong> coins and Bob the last one.\nThe maximum number of coins which you can have are: 7 + 2 = 9.\nOn the other hand if we choose this arrangement (1, <strong>2<\/strong>, 8), (2, <strong>4<\/strong>, 7) you only get 2 + 4 = 6 coins which is not optimal.\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> piles = [2,4,5]\n<strong>Output:<\/strong> 4\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> piles = [9,8,7,6,5,1,2,3,4]\n<strong>Output:<\/strong> 18\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>3 &lt;= piles.length &lt;= 10^5<\/code><\/li><li><code>piles.length % 3 == 0<\/code><\/li><li><code>1 &lt;= piles[i] &lt;= 10^4<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<p>Always take the second largest element of a in the sorted array.<br>[1, 2, 3, 4, 5, 6, 7, 8, 9]<br>tuples: (1, 8, 9), (2, 6, 7), (3, 4, 5)<br>Alice: 9, 7, 5<br>You: 8, 6, 4<br>Bob: 1, 2, 3<\/p>\n\n\n\n<p>Time complexity: O(nlogn)  -&gt; O(n + k)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int maxCoins(vector<int>& piles) {\n    const int n = piles.size() \/ 3;\n    sort(begin(piles), end(piles));\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      ans += piles[n * 3 - 2 - i * 2];\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ counting sort<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int maxCoins(vector<int>& piles) {\n    constexpr int kMax = 10000;\n    const int n = piles.size() \/ 3;\n    vector<int> counts(kMax + 1);\n    for (int v : piles) ++counts[v];\n    int idx = 0;\n    for (int i = 1; i <= kMax; ++i)\n      while (counts[i]--) piles[idx++] = i;\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      ans += piles[n * 3 - 2 - i * 2];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are 3n&nbsp;piles of coins of&nbsp;varying size, you and your friends will take piles of coins as follows: In each step, you will choose&nbsp;any&nbsp;3 piles&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177],"class_list":["post-7297","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7297","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=7297"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7297\/revisions"}],"predecessor-version":[{"id":7384,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7297\/revisions\/7384"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}