1561. Maximum Number of Coins You Can Get

题目信息

题号:

1561

难度:

Medium

主题:

数组、排序、贪心

原题:

LeetCode 1561

重点:

每轮从剩余堆中选三堆,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。