LeetCode 1561. 你可以获得的最大硬币数目
题目描述
题意分析
总共有
3g堆硬币，每轮可以任意选三堆：Alice 先拿最多的一堆，你拿剩下较多的一堆，Bob 拿最后一堆。经过g轮分完所有硬币，求你的最大总数。你能决定如何分组，但每份所得都必须有一堆至少同样大的硬币让 Alice 先拿走，因此不能直接选择最大的
g堆。
解法：排序 + 贪心
核心思路
[!blue]
先把所有堆升序排序。让 Bob 消耗最小的
g堆，把剩下的2g堆从小到大相邻配对，每对中较大的给 Alice、较小的给你。Bob 的每一堆都不大于这些配对中的任何一堆，任意分配给各轮都符合三人的取走顺序。这个构造达到了每份所得的上界。把你拿到的堆按降序排列，考虑其中第
k大的一堆：前k份所得都不小于它，且各自还要有一份 Alice 的选择不小于自己，所以原数组中至少有2k堆不小于它。于是你的第k大所得，不可能超过原数组的第2k大。上面的相邻配对恰好让你拿到原数组第
2、4、...、2g大的堆，同时达到这些逐项上界，因此总和最大。换成升序下标，就是从g开始，每隔一项累加一次。
解题步骤
- 将
piles升序排序，令轮数groups = piles.length / 3。- 前
groups堆留给 Bob，从下标groups开始处理剩余配对。- 每对的第一堆是你的所得，累加后下标增加
2，跳过 Alice 的一堆。- 返回累加结果。排序会直接重排输入数组。
代码实现
class Solution {
public int maxCoins(int[] piles) {
Arrays.sort(piles);
int groups = piles.length / 3;
int answer = 0;
// 最小的一组留给第三人，之后每对取较小堆，右侧较大堆给先选者。
for (int i = groups; i < piles.length; i += 2) {
answer += piles[i];
}
return answer;
}
}
import "sort"
func maxCoins(piles []int) int {
sort.Ints(piles)
groups := len(piles) / 3
answer := 0
// 最小的一组留给第三人，之后每对取较小堆，右侧较大堆给先选者。
for i := groups; i < len(piles); i += 2 {
answer += piles[i]
}
return answer
}
复杂度分析
- 时间复杂度：$O(N\log(N+1))$，其中
N是硬币总堆数，排序占主导。- 空间复杂度：扫描额外使用 $O(1)$ 空间，排序工作区另计；输入会被重排。
关键点总结
[!green]
- 每份所得都需要一份不小于它的 Alice 配对，因此第
k大所得受第2k大原始堆限制。- 把最小的
g堆交给 Bob，再配对剩余堆，能同时达到所有排名上界。- 同样大小的两堆可以配对，Alice 的堆不必严格大于你的堆。
易错点总结
[!yellow]
- 直接拿最大的
g堆，忽略了 Alice 每轮都先取一堆的限制。- 从数组开头隔项累加，会把应当交给 Bob 的小堆计入你的所得。
- 从
groups开始后要每次跳两项，逐项累加会把 Alice 的堆也计算进去。- 这里每轮能任意选三堆，不受原数组位置是否连续的限制，排序分组才可直接实现。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 561. 数组拆分 | 简单 | 同样排序后安排各组角色，本题把最小值留给Bob、最大值给Alice，再最大化自己拿到的次大值。 |
| 1877. 数组中最大数对和的最小值 | 中等 | 同样通过交换论证安排排序后的分组，但原题控制两项和，本题按三人取值角色决定贡献。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！