1561. Maximum Number of Coins You Can Get¶
题目信息¶
- 题号:
1561
- 难度:
Medium
- 主题:
数组、排序、贪心
- 原题:
- 重点:
每轮从剩余堆中选三堆,Alice 取最大、你取第二大、Bob 取最小;最大化你得到的硬币数
题目重述¶
给定长度为 3n 的正整数数组 piles,每个元素表示一堆硬币数量。每轮从剩余堆中选择三堆:Alice 取得其中最大的一堆,你取得第二大的一堆,Bob 取得最小的一堆。
重复直到所有堆都被取走。请返回通过合理选择每轮三堆,你能够获得的最大硬币总数。
3 <= piles.length <= 10^5,长度是 3 的倍数,1 <= piles[i] <= 10^4。
自建示例¶
应把最小堆留给 Bob,并成对使用较大的堆:
输入:piles = [2,4,1,2,7,8]
输出:9
解释:可分为 [1,7,8] 和 [2,2,4],你分别得到 7 和 2。
只有三堆时你取得中间值:
输入:piles = [1,2,3]
输出:2
解释:Alice 取 3,你取 2,Bob 取 1。