牛客每日一题+Tracker刷题复盘：乐团派对贪心思路全解析

前阵子刷牛客的每日一题，正好碰到一道叫“乐团派对”的题，加上我一直用自己搭的一套 tracker 在做刷题记录，那次就顺手把整个过程完整复盘了一遍：从最初读题时想当然，到后面把解法、证明、边界条件都理清楚，再更新到 tracker 里。这套组合拳跑下来，效果比单纯刷题好不少。所以想单独写一篇，把我用的 tracker 模板和这道题的贪心思路都拿出来聊一聊。

先说结论：这道“乐团派对”并不难，但它非常适合用来检验你对“排序贪心”这类题型的掌握程度。它表面上是组队问题，实际上是一个判断“什么时候该果断截断一组”的决策题。而牛客的每日一题 + tracker 的组合，则是我目前用过最稳的刷题节奏：每天一道题不会造成负担，tracker 又能把每一道题沉淀成可检索、可复习的个人题库。无论你是刚准备刷题的新手，还是已经刷了几百题想系统化整理的老手，这套玩法都值得看看。

1. 为什么要把每日一题和 Tracker 绑在一起

1.1 每日一题解决“刷什么”的问题

刷题最消耗意志力的不是做题，而是选题。打开题库，几千道题摆在面前，难度参差不齐，标签五花八门，你很容易在“做哪道”这件事上浪费半小时，然后焦虑地关掉页面。牛客的每日一题本质上就是把“选题”这个决策外包出去，平台帮你挑好一道有代表性的题，你今天只需要面对一个问题：把它做出来。

我个人的体会是，每日一题的价值不在于题目本身难不难，而在于它形成了一种固定的节奏。就像健身的人不需要每天纠结练哪个部位，跟着课表走就行。刷题也一样，每天打开页面，题已经在那了，直接进入思考状态，反而更容易坚持。尤其是工作之后，整块的学习时间被切碎，每天花半小时到一小时在一道题上，是比较现实的投入产出比。

1.2 Tracker 解决“刷完就忘”的问题

只刷题不复盘，相当于往漏水的桶里倒水。我见过不少朋友刷了三四百题，回头问他一周前做过的那道题用什么思路，他完全想不起来。这不是记忆力的问题，而是缺少一个“把题目沉淀下来”的动作。

Tracker 就是干这个的。它不需要很复杂，核心就三件事：记录、统计、复习。记录让你知道做过什么，统计让你知道自己的薄弱点在哪，复习让你真正把思路内化。我把 tracker 理解为刷题版的“知识账本”，每一道 AC 的题目都是你存进去的一笔资产，而你给它贴上的标签、写的复盘，就是这笔资产的索引。没有索引的资产，很快就找不到了。

很多人在网上找各种现成的刷题打卡表格，但我更建议自己搭建一个，因为只有你自己才知道需要记录什么字段。比如我自己的 tracker 里，“是否独立 AC” 和 “首次用时” 就是必填项，因为它们能反映真实掌握程度。别人做的模板可能更通用，但未必贴合你的节奏。

1.3 Tracker 应该记录哪些字段

我的 tracker 用的是一张简单的在线表格，字段不多，但每一个都是我踩过坑之后觉得不能省的。这里直接放出我常用的字段表：

这套模板的核心逻辑是“一题一行”。每次 AC 之后花两到三分钟把表格填掉，后面整理复习的时候能省出大量时间。我后面聊“乐团派对”的时候，也会按这套字段把它填进 tracker，到时候你就知道每一列是怎么用的了。

2. “乐团派对”这道题到底在考什么

2.1 题目抽象与模型转化

先把题意抽象出来。假设一共有 n 个人要参加乐团派对，第 i 个人给出一个期望值 a[i]，表示他所在的队伍人数“不少于”a[i] 才愿意参加。现在要求你把这 n 个人分成若干组，每个组的人数要满足组内所有人的期望值，目标是把有效组数做到最大。

翻译成人话就是：每个人对团队最小规模有要求，有人觉得 2 个人就能组队，有人非要至少 5 个人才愿意上台。你作为组织者，要在满足所有人要求的前提下，尽可能拆出更多的队伍。

这里核心的模型是一个分组可行性判断：一组大小为 size 的队伍是合法的，当且仅当这一组里所有人的 a[i] 都不超过 size。也就是说，队伍的人数由组内需求最大的人决定。这个结论看起来简单，但很多人的解法是从这里开始跑偏的。

2.2 为什么第一反应是排序 + 贪心

这类“每个人有最低要求，问最多能分成几组”的问题，最自然的想法就是把人的需求从小到大排序，然后从左往右扫，攒够一波就成组。这个方向是对的，因为需求的顺序决定了决策的先后：需求低的人好满足，需求高的人难满足，先安排容易满足的人，能把难满足的人留到后面更大的组里去。

但这里有个特别容易踩的坑：排序之后，到底按什么条件截断？有人写成“当前组人数大于等于当前这个人的需求”，有人写成“当前组人数等于当前这个人的需求”，还有人写成“严格大于需求”。差一个字，结果可能完全不同，具体用哪个必须回到题目描述里抠字眼。题目说的是“不少于 a[i] 人”，那判断条件就是当前组人数 >= a[i]。

我再解释一下这个截断为什么是正确的。假设排序后数组为 a[0] <= a[1] <= ... <= a[n-1]，我们从左往右把每个人放进当前组，同时记录当前组人数 cnt。如果 cnt >= a[i]，说明当前这个人的需求已经被满足，而由于数组是升序的，前面加入组里的所有人的需求都不超过 a[i]，所以整个组的合法性也同时被满足了。这时候把一组截断出来，不会破坏任何人的要求，而且让组数增加了 1。

如果你选择不在这里截断，继续往后塞人，会发生什么？后续加入的人需求只可能更大，当前组的规模虽然变大了，但组数没变多，反而消耗了更多本来可以在后面组成新组的人。所以“能截断就截断”就是局部最优，而且能堆出全局最优。

2.3 完整推导一个样例

我拿一个例子手动跑一遍，大家感受一下这个贪心过程。假设 n = 6，a = [4, 3, 1, 5, 5, 1]。排序之后变成 [1, 1, 3, 4, 5, 5]。

从左往右扫描：

1. 当前组人数 cnt = 0。遇到第一个人 a[0] = 1，cnt 变成 1，1 >= 1 成立，截断第一组，组数 ans = 1，cnt 重置为 0。
2. 遇到 a[1] = 1，同样 cnt = 1 >= 1，截断第二组，ans = 2。
3. 遇到 a[2] = 3，cnt = 1，1 < 3，不能截断，继续。
4. 遇到 a[3] = 4，cnt = 2，2 < 4，不能截断，继续。
5. 遇到 a[4] = 5，cnt = 3，3 < 5，不能截断，继续。
6. 遇到 a[5] = 5，cnt = 4，4 < 5，遍历结束，剩余 4 个人无法组成合法队伍。

最终 ans = 2。也就是说，这 6 个人最多只能组成两个有效队伍：第一队单人（a = 1 的人），第二队单人（另一个 a = 1 的人），剩下的 4 个人因为至少都要 3 人以上的队伍，而剩余人数不足 5，无法成组。这个结果乍看有点反直觉：明明有 6 个人，怎么就只组成 2 队？因为两个需求为 1 的人如果选择和后面的人组大组，反而会浪费人数，导致组数更少。

为了验证，我们可以试另一个分组方案：把两个 a = 1 的人和一个 a = 3 的人组成一个 3 人队，另外三个 a = 4, 5, 5 的人组成一个 5 人队，组数也是 2。所以贪心的结果 2 是这个样例下的最优解。

3. 这道题的代码实现与边界处理

3.1 C++ 参考实现

题目模型清楚之后，代码其实非常短。这里给出 C++ 的实现：

#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int n; cin >> n; vector<ll> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } sort(a.begin(), a.end()); ll cnt = 0, ans = 0; for (int i = 0; i < n; ++i) { cnt++; if (cnt >= a[i]) { ans++; cnt = 0; } } cout << ans << "\n"; return 0; }

核心逻辑就 7 行。很多人会觉得这么短的代码，凭什么能当每日一题？但恰恰是这种“代码短、证明难”的题目最适合训练思维。你写的每一行都有讲究：为什么要排序？为什么截断条件用 >= 而不是 >？为什么最后不用处理剩余的人？这些问题比代码本身重要得多。

3.2 边界条件与数据范围

边界情况是这种贪心题最容易翻车的地方，我比赛和刷题时吃过太多亏，这里列几个出来：

单个人的情况。假设 n = 1，a[0] = 1，排序后 cnt 加 1，1 >= 1 成立，输出 1。如果 a[0] = 2，cnt = 1 < 2，循环结束，输出 0。这个结果是对的：一个人无法组成 2 人的队伍，就算他自己愿意也组不起来。

全是大需求的极端情况。比如 n = 10，每个人需求都是 100，排序后从头扫到尾，cnt 最多到 10，始终小于 100，最终 ans = 0。这里要注意，不要因为“人数不足”就试图把不同需求的打散重组，重组的前提是满足所有人的需求，10 个人无论如何也变不成 100 人，所以 0 是正确答案。

数据范围问题。n 可能很大，a[i] 也可能很大，所以计数变量建议用 long long。有些同学在本地样例能过，交上去 WA，就是 int 溢出。这道题虽然看起来简单，一旦 n 到 10 的 6 次方级别，人数累计的逻辑用 int 真的可能溢出，刷题时养成用 long long 的习惯能省很多事。

严格大于与不小于的区别。题目如果改成“队伍人数必须严格大于 a[i]”，判断条件就要变成 cnt > a[i]。这是一个典型的读题陷阱，比赛里经常有人因为没看清这句话，样例都过不了。我建议在 tracker 的“核心思路”字段里专门加一句“此处为 >= / >”，方便以后复习时一眼想起这个坑。

4. 完整实操复盘：从读题到 AC 再到 Tracker

4.1 我的做题心路与一血教训

我来讲一下自己当时做这道题的真实过程。打开牛客的每日一题页面，看到“乐团派对”这个标题，我第一反应是这题会不会是模拟题，毕竟“派对”听起来像是一堆人坐在一起。读完题之后发现是分组问题，第一想法是“这题是不是动态规划”，因为分组类问题很容易往 DP 上想，比如区间 DP 或者背包。

但是我看了一眼数据范围，n 的规模很大，显然不是 O(n^2) DP 能扛住的，于是开始往排序方向想。当时我手推了几组小例子，比如 [1, 1, 3, 4, 5, 5]，发现升序排列后“能截断就截断”是合理的，所以直接写了上一节的代码，样例也过了。

不过我没有急着提交，而是先自己构造了一个稍微刁钻的例子：a = [2, 2, 2, 2, 2, 2]。排序后全是 2，从左扫：cnt = 2 时截断一组，再来两个人截断第二组，最后剩下 2 个人，ans = 2。我一度担心这是不是最优的，后来想想，6 个人每组至少 2 人，最多也只能分 3 组。等等，6 除以 2 等于 3，为什么我的答案是 2？是不是代码有 bug？

这里是我事后想明白的一个关键点：前两组各 2 人消耗了 4 个人，剩下 2 个人确实可以再组成一组，所以 ans 应该是 3 而不是 2。我那次被自己绕进去了，后来重新跑了一遍：i = 0 时 cnt = 1；i = 1 时 cnt = 2，2 >= 2 成立，ans = 1，cnt = 0；i = 2 时 cnt = 1；i = 3 时 cnt = 2，2 >= 2 成立，ans = 2，cnt = 0；i = 4 时 cnt = 1；i = 5 时 cnt = 2，2 >= 2 成立，ans = 3，cnt = 0。所以答案是 3，代码没有问题。这个例子说明，手推样例时不能只算一半，一定要完整走完整个循环。

4.2 借助暴力对拍验证贪心

如果只是样例和手推几个小例子，我其实还是不太放心。因为贪心策略最怕的是“看起来对，但实际上在某个角落藏着反例”。所以我那天额外做了一件事：写了一个 DFS 暴力和贪心对拍。

对拍的做法是这样的：先用程序随机生成 n 很小、a[i] 也较小的一组数据，然后用一个递归搜索枚举所有可能的分组方式，求出真正的最优组数，再用贪心算法跑同一组数据，比较两个结果是否一致。随机生成几千组小数据，如果全部一致，贪心策略的可信度就高很多。

这里我用 Python 快速写了一个暴力验证脚本，形式大概是：

from functools import lru_cache def brute(a): n = len(a) best = 0 def dfs(i, group_max, size): nonlocal best if i == n: if size == 0: best = max(best, 0) return # 把当前人放进当前组 if size > 0: dfs(i + 1, max(group_max, a[i]), size + 1) else: dfs(i + 1, a[i], 1) # 以当前组为最后一组，结束分组 if size > 0 and group_max <= size: best = max(best, best + 1) # 这个写法等效，仅示意 # 如果当前组已经满足要求，可以截断后开启新组 if size > 0 and group_max <= size: dfs(i + 1, a[i], 1) # 这个暴力写法需要小心，实际对拍时我封装了完整的递归

上面这段只是一个简化示意，实际上我的暴力脚本写得更直接：枚举每个元素属于哪个组。对拍跑了大概五千组随机小数据，贪心结果全部和暴力一致，这时候我才放心地提交。对拍这种手段，强烈建议大家在刷题时养成习惯，尤其是贪心题。它不能替代数学证明，但能高效地把你的思路从“大概正确”提升到“实测正确”。

4.3 把这道题更新进 Tracker

AC 之后不要直接关页面，接下来才是 tracker 发挥作用的时刻。我当时填的内容大概是这样的：

日期：某月某日；题号：牛客每日一题当天题号；题目名称：乐团派对；核心标签：贪心、排序；难度自评：★★（思路短但需要证明；对新手是三星难度）；是否独立 AC：否（我看了一眼讨论区里“贪心能过”的提示才确定方向）；首次用时：40 分钟；错误次数：0；核心思路：升序排序，从左往右统计人数，cnt >= a[i] 时立刻成组；复杂度：O(n log n) / O(1)；复盘链接：对应的博客草稿。

这一行填完，这道题才算真正变成了我的资产。以后我做题遇到类似“分组要求人数不少于 xxx”的题目时，只需要在 tracker 里搜“贪心”标签，就能翻出这一行，花 30 秒回忆一下核心思路，就知道这类题的通用解法是什么了。

5. 常见问题与排查技巧实录

5.1 题目层面的坑

这道题以及同类题目，我总结出三个高频问题：第一个就是读题粗细的问题，把“不少于 a[i]”看成“恰好等于 a[i]”。一旦理解成“恰好等于”，代码就会变成在等式中找精确匹配，样例可能碰巧能过，但提交基本会错。我建议读题时把关键约束条件在纸上抄一遍，标出是 >= 还是 >，是“最多能组成多少组”还是“最少要分成多少组”。

第二个是贪心方向搞反的问题。有人喜欢从大到小排序，然后从需求最大的人开始组队。这个方向不是完全不能做，但处理起来会比较别扭。因为需求最大的人会拉高当前组的最小规模，如果你一直把后面需求小的人塞进来，会导致整个组特别大，组数变少。从小到大排序、能截断就截断，是更省心的方向。

第三个是解释不了为什么贪心是对的。面试或者周赛复盘时，经常会被追问“为什么这个贪心是成立的”。只说出结论而没有论证，说服力是不够的。我习惯用一个简单的交换论证来组织语言：假设最优解里有某个组的规模大于它实际需要的规模，就是组内有多余人，这些人本来可以拆分出来组成新组，那么“能截断就截断”的策略不会比最优解差。这样讲，对方就能理解你的思路来源。

5.2 Tracker 使用层面的坑

工具用起来也不是一帆风顺的，我的 tracker 就经历过三次调整，每一次都是因为发现原来的设计有问题。

最初我只记录题号和 AC 状态，过了两个月想按标签复习，发现完全没有标签信息，根本不知道怎么筛。后来加了“核心标签”和“核心思路”，检索方便了，但新的问题出现了：标签命名不统一。比如我有时候写“贪心”，有时候写“greedy”，有时候写“排序贪心”，统计时直接乱掉。所以后来我固定了一个标签清单，所有题目的标签只能从中选取，这样统计报告才有意义。

还有一个坑是只记录不复习。Tracker 不是写完了就扔的，我的建议是每周花十分钟看一遍本周记录，标出那些“是否独立 AC = 否”的题，这些就是二刷队列。二刷时不需要重新写完整代码，只需要拖到 IDE 里，先看题号，回忆思路，写一个骨架出来，然后对照原来填的“核心思路”看看有没有偏移。这个过程比做新题有用得多。

5.3 常见问题速查表

6. 一些个人的坚持与体会

这套“牛客每日一题 + 自己的 tracker”的组合，我实际用了大半年。最大的变化倒不是 AC 数量涨了多少，而是每次做题之后都有一个明确的知识归位动作：这道题考了什么标签、用了什么思路、下次遇到怎么识别。这种“做了就沉淀”的感觉，让我不再焦虑刷过的题会丢掉。

如果让我给一个最实在的建议：每周固定一个时间，把 tracker 里“是否独立 AC = 否”的题目统一过一次，比刷十道新题更值。我当时坚持到第二个月的时候，明显感觉很多在周赛里遇到的题，虽然没见过原题，但“这不就是我 tracker 里某类题换个皮”的感觉会变得非常频繁。那种熟悉感，就是刷题系统化之后的正反馈。

最后再分享一个小技巧：填“核心思路”时，不要写长篇大论，一句话就够了，但要用自己的语言。比如“升序排序，攒人，够了就成组”，这种话别人看来可能太随意，但三个月后的你自己看到时，会比看题解的几十行推导更快地想起来。tracker 是服务未来的自己的，不是为了给别人看的，所以越符合自己的表达习惯越好。