LeetCode 1561. 你可以获得的最大硬币数目

约 4 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 快手
标签
数组 数学 排序 贪心 博弈
目录

题目描述

✅ 1561. 你可以获得的最大硬币数目

题意分析

一共有 3n 堆硬币，三个人分 n 轮取完。每轮由「我」自由挑出任意 3 堆，然后 Alice 拿走这 3 堆里最大的一堆，我拿走中间的那堆，Bob 拿走最小的那堆。问我最多能拿到多少枚硬币。

分组权在我手上，这是全题唯一的自由度。Alice 和 Bob 的行为完全被规则锁死——组一旦定下，谁拿哪堆没有任何悬念。所以这不是博弈对抗，而是一道「怎么分组最优」的构造题。

我在每组里永远只能拿第二名，这条约束决定了策略形态：任何一堆想被我拿到，就必须给它配一堆比它更大的当挡箭牌（喂给 Alice），再配一堆比它更小的（喂给 Bob）。挡箭牌越便宜、垫底的越便宜，我留给自己的就越贵。

piles 的长度保证是 3 的倍数，n 可以到 $10^5$（总长 $3 \times 10^5$），元素值到 $10^4$。总和最大约 $3 \times 10^9$，会超过 int 上限的一半但不到全部——实际答案约为总和的一半以下，用 int 恰好还能装下，不过累加时仍要有意识。

枚举分组方案的数量是天文数字，规模在提示答案要靠排序加一次线性扫描直接构造。

边界上 n = 1 时只有 3 堆，我必然拿中间那堆，答案就是排序后的中位数。

解法：排序 + 贪心

核心思路

每轮三堆中 Alice 取最大、我取次大、Bob 取最小。Bob 的选择不计入答案，因此应让他消耗全局最小的 n 堆；剩余 2n 堆只需分配给 Alice 和我。

将所有堆升序排序。对剩余部分从大到小两两配对：每对中较大者给 Alice，较小者给我。换成升序下标，我拿到的位置就是 n,n+2,...,3n-2。

这个构造达到任何方案都无法突破的上界：在任意分组中，我拿到的第 k 大堆都需要对应 k 堆不小于它的硬币供 Alice 取走，因此它不可能超过全局第 2k 大的元素。将全局降序排名 1,3,...,2n-1 给 Alice、2,4,...,2n 给我，再把剩余最小的 n 堆给 Bob，恰好同时达到所有这些排名上界。该论证只需要“不小于”，同值硬币堆也完全适用。

不变量：扫描下标 n,n+2,... 时，已累加的每一堆都与紧邻右侧的一堆组成 Alice/我的一对，而最小的 n 堆留给 Bob；所有使用过的堆互不重复。 扫描结束正好形成 n 个合法三元组。

解题步骤

  1. 升序排序 piles。
  2. 令 groups = piles.length/3。
  3. 从下标 groups 开始，每隔一个元素累加一次，直到数组末尾。
  4. 返回累加结果。

对 [9,8,7,6,5,1,2,3,4]，排序后最小的 1,2,3 给 Bob；我取得下标 3,5,7 的 4,6,8，答案为 18。边界只有三堆时，排序后直接取得中间值。

代码实现

import java.util.Arrays;

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
}

复杂度分析

设硬币堆数为 m。

  • 时间复杂度： $O(m\log m)$，排序占主导。
  • 空间复杂度： 除标准库排序所需空间外为 $O(1)$；排序通常使用 $O(\log m)$ 级别的栈空间。

关键点总结

  • Bob 对答案无贡献，最小的 n 堆应作为每组最小值被消耗。
  • 剩余堆中，我每取一堆都需要一堆不小于它的硬币给 Alice。
  • 从大到小相邻配对达到偶数排名上界，证明贪心最优。
  • 升序实现对应从下标 n 开始、步长为 2 的累加。

易错点总结

  • 不排序直接按下标取值： 原下标与大小排名无关。
  • 从下标 0 开始： 会把应留给 Bob 的最小堆计入答案，且取超过 n 堆。
  • 步长写成 3： 剩余部分是 Alice 与我两两配对，步长应为 2。
  • 认为 Alice 的堆必须严格更大： 堆大小可以相等，角色由每轮取堆顺序决定。
  • 降序排序后仍使用升序下标公式： 降序时应取下标 1,3,...,2n-1。

相似题目

题目 难度 考察点
561. 数组拆分 简单 同样是排序后按固定步长取值，但要最大化每对的最小值之和
881. 救生艇 中等 排序后首尾双指针配对，配对规则由容量上限而非大小顺序决定
870. 优势洗牌 中等 田忌赛马式配对，需要用最小的可胜牌去压对手，还要还原原始顺序
455. 分发饼干 简单 双数组分别排序后双指针贪心匹配，目标是最大化满足人数
1029. 两地调度 中等 按两种代价之差排序，前一半与后一半各归一边，同属排序后切两段
976. 三角形的最大周长 简单 排序后只需检查相邻三元组，靠单调性证明无需回头搜索
1679. K 和数对的最大数目 中等 配对目标是固定和，可用哈希计数替代排序，配对次数即为答案