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
Intuition:
玩家每次可以拿到剩余堆数中第二大堆的金币
所以可以拿到前2/3中第偶数堆数量的金币
Approach:
排序之后拿前2/3堆偶数堆的金币
TS Code:
function maxCoins (piles: number[]): number {
piles.sort((a, b) => b - a)
let result = 0
for (let i = 1; i < piles.length / 3 * 2; i += 2) {
result += piles[i]
}
return result
}