|
| 1 | +/* |
| 2 | +
|
| 3 | +-* 1561. Maximum Number of Coins You Can Get *- |
| 4 | +
|
| 5 | +
|
| 6 | +
|
| 7 | +There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows: |
| 8 | +
|
| 9 | +In each step, you will choose any 3 piles of coins (not necessarily consecutive). |
| 10 | +Of your choice, Alice will pick the pile with the maximum number of coins. |
| 11 | +You will pick the next pile with the maximum number of coins. |
| 12 | +Your friend Bob will pick the last pile. |
| 13 | +Repeat until there are no more piles of coins. |
| 14 | +Given an array of integers piles where piles[i] is the number of coins in the ith pile. |
| 15 | +
|
| 16 | +Return the maximum number of coins that you can have. |
| 17 | +
|
| 18 | +
|
| 19 | +
|
| 20 | +Example 1: |
| 21 | +
|
| 22 | +Input: piles = [2,4,1,2,7,8] |
| 23 | +Output: 9 |
| 24 | +Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one. |
| 25 | +Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one. |
| 26 | +The maximum number of coins which you can have are: 7 + 2 = 9. |
| 27 | +On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal. |
| 28 | +Example 2: |
| 29 | +
|
| 30 | +Input: piles = [2,4,5] |
| 31 | +Output: 4 |
| 32 | +Example 3: |
| 33 | +
|
| 34 | +Input: piles = [9,8,7,6,5,1,2,3,4] |
| 35 | +Output: 18 |
| 36 | +
|
| 37 | +
|
| 38 | +Constraints: |
| 39 | +
|
| 40 | +3 <= piles.length <= 105 |
| 41 | +piles.length % 3 == 0 |
| 42 | +1 <= piles[i] <= 104 |
| 43 | +
|
| 44 | +
|
| 45 | +*/ |
| 46 | + |
| 47 | +classSolution { |
| 48 | +intmaxCoins(List<int> piles) { |
| 49 | +int m=0; |
| 50 | +finalint n= piles.length; |
| 51 | + |
| 52 | +for (int xin piles) { |
| 53 | +if (x> m) { |
| 54 | + m= x; |
| 55 | + } |
| 56 | + } |
| 57 | + |
| 58 | +finalList<int> hash=List<int>.filled(m+1,0); |
| 59 | + |
| 60 | +for (int xin piles) { |
| 61 | + hash[x]++; |
| 62 | + } |
| 63 | + |
| 64 | +int bobCoin= n~/3; |
| 65 | +int startIndex=1; |
| 66 | + |
| 67 | +while (bobCoin>0) { |
| 68 | +if (hash[startIndex]>0) { |
| 69 | + hash[startIndex]--; |
| 70 | + bobCoin--; |
| 71 | + }else { |
| 72 | + startIndex++; |
| 73 | + } |
| 74 | + } |
| 75 | + |
| 76 | +int i= m; |
| 77 | +int ans=0; |
| 78 | +int receive=0; |
| 79 | + |
| 80 | +while (i>= startIndex) { |
| 81 | +if (hash[i]>0) { |
| 82 | + ans+= receive* i; |
| 83 | + receive= receive^1; |
| 84 | + hash[i]--; |
| 85 | + }else { |
| 86 | + i--; |
| 87 | + } |
| 88 | + } |
| 89 | + |
| 90 | +return ans; |
| 91 | + } |
| 92 | +} |