Re: [閒聊] 每日LeetCode
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700794643.A.659.html
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 534 之 719 篇)：