※ 引述《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: