※ 引述《ZooseWu (動物園 公告)》之銘言:
: 1561. Maximum Number of Coins You Can Get
: 桌上有3n堆金幣,你和你的兩位朋友依照下面規則拿金幣:
: 1.你從中選出三堆金幣
: 2.Alice從三堆金幣中拿數量最高的一堆金幣
: 3.你從剩下兩堆金幣中拿一堆金幣
: 4.Bob拿最後剩下的金幣
: 5.回到第一步
: 回傳你最多能獲得的金幣數量
: Input: piles = [2,4,1,2,7,8]
: Output: 9
: 你選出[2,7,8]出來,Alice拿走8個金幣,你拿走7個金幣,Bob拿走1個金幣
: 你選出[1,2,4]出來,Alice拿走4個金幣,你拿走2個金幣,Bob拿走1個金幣
: Input: piles = [2,4,5]
: Output: 4
: Input: piles = [9,8,7,6,5,1,2,3,4]
: Output: 18
: [9,8,1]=>9=>8=>1
: [7,6,2]=>7=>6=>2
: [5,4,3]=>5=>4=>3
: 8+6+4=18
思路:
1.最簡單的作法就用一個MaxHeap,每次pull兩個元素累加第二個元素,直到pull到
指定次數,只是跑出來的時間複雜度滿爛的。
2.題目給的測資滿適合計數排序的,counting之後3ms就AC了。
Java Code: