前阵子刷牛客的每日一题正好碰到一道叫“乐团派对”的题加上我一直用自己搭的一套 tracker 在做刷题记录那次就顺手把整个过程完整复盘了一遍从最初读题时想当然到后面把解法、证明、边界条件都理清楚再更新到 tracker 里。这套组合拳跑下来效果比单纯刷题好不少。所以想单独写一篇把我用的 tracker 模板和这道题的贪心思路都拿出来聊一聊。先说结论这道“乐团派对”并不难但它非常适合用来检验你对“排序贪心”这类题型的掌握程度。它表面上是组队问题实际上是一个判断“什么时候该果断截断一组”的决策题。而牛客的每日一题 tracker 的组合则是我目前用过最稳的刷题节奏每天一道题不会造成负担tracker 又能把每一道题沉淀成可检索、可复习的个人题库。无论你是刚准备刷题的新手还是已经刷了几百题想系统化整理的老手这套玩法都值得看看。1. 为什么要把每日一题和 Tracker 绑在一起1.1 每日一题解决“刷什么”的问题刷题最消耗意志力的不是做题而是选题。打开题库几千道题摆在面前难度参差不齐标签五花八门你很容易在“做哪道”这件事上浪费半小时然后焦虑地关掉页面。牛客的每日一题本质上就是把“选题”这个决策外包出去平台帮你挑好一道有代表性的题你今天只需要面对一个问题把它做出来。我个人的体会是每日一题的价值不在于题目本身难不难而在于它形成了一种固定的节奏。就像健身的人不需要每天纠结练哪个部位跟着课表走就行。刷题也一样每天打开页面题已经在那了直接进入思考状态反而更容易坚持。尤其是工作之后整块的学习时间被切碎每天花半小时到一小时在一道题上是比较现实的投入产出比。1.2 Tracker 解决“刷完就忘”的问题只刷题不复盘相当于往漏水的桶里倒水。我见过不少朋友刷了三四百题回头问他一周前做过的那道题用什么思路他完全想不起来。这不是记忆力的问题而是缺少一个“把题目沉淀下来”的动作。Tracker 就是干这个的。它不需要很复杂核心就三件事记录、统计、复习。记录让你知道做过什么统计让你知道自己的薄弱点在哪复习让你真正把思路内化。我把 tracker 理解为刷题版的“知识账本”每一道 AC 的题目都是你存进去的一笔资产而你给它贴上的标签、写的复盘就是这笔资产的索引。没有索引的资产很快就找不到了。很多人在网上找各种现成的刷题打卡表格但我更建议自己搭建一个因为只有你自己才知道需要记录什么字段。比如我自己的 tracker 里“是否独立 AC” 和 “首次用时” 就是必填项因为它们能反映真实掌握程度。别人做的模板可能更通用但未必贴合你的节奏。1.3 Tracker 应该记录哪些字段我的 tracker 用的是一张简单的在线表格字段不多但每一个都是我踩过坑之后觉得不能省的。这里直接放出我常用的字段表字段填写内容为什么必须记录日期做题当天日期方便统计每周/每月刷题节奏题号牛客或 OJ 上对应题号检索原始题目的唯一入口题目名称题目标题识别不靠题号直接看名字也能想起来核心标签如排序、贪心、DP、二分后续统计薄弱标签难度自评1~5 星独立于平台难度平台难度有时不匹配个人感受是否独立 AC是/否决定这道题要不要进入二刷队列首次用时15分钟/30分钟/1小时反映对同类题型的熟练度错误次数0/1/2/3高频错题需要重点复盘核心思路一两句话概括解法要点复习时不用重新看题解复杂度时间/空间复杂度强化复杂度意识复盘链接博客或笔记地址想看详细推导时直接跳转这套模板的核心逻辑是“一题一行”。每次 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 6a [4, 3, 1, 5, 5, 1]。排序之后变成 [1, 1, 3, 4, 5, 5]。从左往右扫描当前组人数 cnt 0。遇到第一个人 a[0] 1cnt 变成 11 1 成立截断第一组组数 ans 1cnt 重置为 0。遇到 a[1] 1同样 cnt 1 1截断第二组ans 2。遇到 a[2] 3cnt 11 3不能截断继续。遇到 a[3] 4cnt 22 4不能截断继续。遇到 a[4] 5cnt 33 5不能截断继续。遇到 a[5] 5cnt 44 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; vectorll 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 1a[0] 1排序后 cnt 加 11 1 成立输出 1。如果 a[0] 2cnt 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 再到 Tracker4.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 1i 1 时 cnt 22 2 成立ans 1cnt 0i 2 时 cnt 1i 3 时 cnt 22 2 成立ans 2cnt 0i 4 时 cnt 1i 5 时 cnt 22 2 成立ans 3cnt 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 把这道题更新进 TrackerAC 之后不要直接关页面接下来才是 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 常见问题速查表现象可能原因解决办法样例能过但提交 WA判断条件写成 而题目要求 回读题面把约束用笔标出来提交时下标越界或溢出数组长度或计数变量用了 int改用 long long检查 n 的范围贪心策略运行结果偏小排序方向反了导致需求大的人过早拉高组规模统一用升序排序能截断就截断手推结果和代码输出不一致手推时没有把循环完整走完用纸笔模拟完整循环或写个脚本验证tracker 标签统计混乱随意使用近义词标签没有统一字典固定标签清单新题只能从清单里选择复习时找不到题目来源只记了题名没记题号补上题号字段并在复盘链接中存原始网页6. 一些个人的坚持与体会这套“牛客每日一题 自己的 tracker”的组合我实际用了大半年。最大的变化倒不是 AC 数量涨了多少而是每次做题之后都有一个明确的知识归位动作这道题考了什么标签、用了什么思路、下次遇到怎么识别。这种“做了就沉淀”的感觉让我不再焦虑刷过的题会丢掉。如果让我给一个最实在的建议每周固定一个时间把 tracker 里“是否独立 AC 否”的题目统一过一次比刷十道新题更值。我当时坚持到第二个月的时候明显感觉很多在周赛里遇到的题虽然没见过原题但“这不就是我 tracker 里某类题换个皮”的感觉会变得非常频繁。那种熟悉感就是刷题系统化之后的正反馈。最后再分享一个小技巧填“核心思路”时不要写长篇大论一句话就够了但要用自己的语言。比如“升序排序攒人够了就成组”这种话别人看来可能太随意但三个月后的你自己看到时会比看题解的几十行推导更快地想起来。tracker 是服务未来的自己的不是为了给别人看的所以越符合自己的表达习惯越好。