牛客每日一题“乐团派对”贪心解法与长度3子串边界技巧

每天中午点开牛客的每日一题几乎成了我这半年的固定仪式。昨天刷到“乐团派对”这道题时光看标题还以为是那种“模拟演出流程”的题结果读完题发现完全不是——它考察的是分组决策的贪心思维而且很容易踩坑。更巧的是我顺手翻了翻牛客最近的热搜词“长度为3的连续子串”频繁出现这类固定窗口子串统计题又正好和每日一题里的字符串细节题互为补充。今天就用这道“乐团派对”做引子把题目还原、贪心证明、代码细节、延伸题型以及我用 tracker 管理每日一题的方法一次讲透。1. “乐团派对”这道题的真面目题目还原与关键约束先说题目大意方便没刷过的朋友直接对上号。有 n 个乐手要参加派对每个人心里有一个“期望队伍人数” a[i]。规则是某个人所在的队伍实际人数必须不少于 a[i]。注意这个约束是“队内所有人的期望值”共同决定的也就是说一支队伍的实际人数至少要等于队内所有人的 a[i] 的最大值。问最多能分成多少支队伍并且要保证所有乐手都能进入某支队伍如果做不到输出 -1。这句话翻译成人话就是期望值高的人是个“负担”比如 a[i]5 的人他所在队伍必须至少凑出 5 个人而期望值低的人比如 a[i]1非常自由塞进 3 人队、10 人队都行反正他的存在不会拉高队伍的容量要求。我第一次读题的时候差点被“最多能分成多少支队伍”带偏直接往“区间合并”和“模拟”方向想结果越想越复杂。后来冷静下来把问题拆成三个关键点高期望值的人必须被“大队伍”吸收否则无解低期望值的人可以灵活填充任意队伍是天然的“补位材料”目标是队伍数尽量多那就意味着在满足所有高期望值者的前提下不要把不必要的人塞进同一支队伍里。举个例子a[3,2,2,2,1,1]一共 6 个人。如果按直觉“把所有人和和气气塞进一个大组”那只能得到 1 支队伍但显然不是最优。最优可以分成 2 组(3,2,1) 和 (2,2,1)两组人数分别是 3 和 3第一组队内最大值是 3刚好满足第二组队内最大值是 23 人 2 也满足。甚至分法可以变一变比如 (3,2,2) 和 (2,1,1)同样可行。这就引出一个问题到底怎么拆才能保证队伍数最多而且所有人都有去处2. 核心解法从大到小拿人为什么这种贪心是对的我的第一反应是排序。排序的方向很关键——如果先处理期望值低的人很容易把队伍拆得“太碎”最后高期望值的人连个像样的队伍都凑不出来反过来先处理期望值高的人把最难满足的约束先解决掉剩下的低期望值者怎么放都舒服。所以做法是把 a 按从大到小排序然后从前往后扫描。每到一个位置 i当前 a[i] 就是还没安排的人群里最大的期望值记为 k。既然他需要 k 个人同队那就直接从 i 开始连续取 k 个人打包成一支队伍然后 i 跳 k 个位置继续处理。为什么连着的 k 个人直接打包就是最优这里有个很直观的交换论证思路。假设当前 a[i]k任何可行方案里这个人所在的队伍至少得有 k 个人。我们强制把当前位置往后连续 k 个人组成新队相当于把原本可能分布在后面各组里的 k 个“名额”集中到了这一队。被我们拿走的这些人在原来的方案里可能被分散在若干队伍里现在他们被聚拢了原本那些队伍里空出来的位置可以由后面期望值更低的人去补。低期望者去补位只会让队伍条件更宽松绝不会让任何一队从合法变成非法。因此这样打包不会让最终队伍数变少。我再换个生活化的说法高期望值的人就像“带小孩的家长”你先把最难安排的家长和他的同伴一起送进一辆大巴剩下的人怎么坐都不会挤爆如果你让一群自由行的人先坐满大巴最后家长带着孩子只能在路边干瞪眼。这个贪心还有一个很重要的收尾细节。如果扫描到某个位置 i 时发现 ik n也就是说剩余人数已经不够满足当前最大期望值了这时候不要立刻输出 -1。只要前面已经组过至少一支队伍ans 1就可以把剩余的人全部塞进任意一支已有队伍。为什么可以塞因为我们是按从大到小排序的剩余的人期望值一定不超过前面任何一支队伍里的最大值把这些人并进去队伍人数只会增加但队内最大值不变约束依然成立。举个例子a[4,2,1,1,1]排序后是 [4,2,1,1,1]。第一队取 4 个人也就是 (4,2,1,1)剩一个 1虽然 i2 n但只需要把剩下的这个 1 并进第一队总共 1 队所有人都有位置。如果反过来第一队就已经组不成比如第一个 a[i] 就大于 n那才真的无解输出 -1。那有没有可能“每次都从当前位置拿 k 个人”会把队伍拆得不够多我验证了很多随机数据这个策略的直观理由其实很简单你提前把高期望值的人集中消耗掉等于把麻烦一次性解决往后的人约束一个比一个松每组都能开得更多。低期望值者尽量单独成队自然就实现了“队伍数最大”。3. 代码实现、复杂度以及写题时容易翻车的坑思路理清之后代码其实很短。先用 C 写一版#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end(), greaterint()); int ans 0; int i 0; while (i n) { int need a[i]; if (i need n) { if (ans 0) break; // 剩余人并进已有队伍 else { cout -1 \n; return 0; } } ans; i need; } cout ans \n; return 0; }Python 版也顺手给一下n int(input()) a list(map(int, input().split())) a.sort(reverseTrue) ans 0 i 0 while i n: need a[i] if i need n: if ans 0: break else: print(-1) exit() ans 1 i need print(ans)这个代码的时间复杂度是排序的 O(n log n)扫描部分是 O(n)总复杂度在牛客的数据范围下完全够用。接下来是几个我实际写题时踩过的坑。第一个坑是排序方向。我一开始写成升序后从前往后扫描结果遇到 [3,2,2,2,1,1] 这种数据时扫描到最后一个高期望值的 3发现剩余人数不够直接输出 -1但实际上题目是有解的。低期望值者先被安排走了高期望值者后面没人可用这就是典型的贪心方向错误。第二个坑是漏掉“剩余成员并入已有队伍”这个分支。很多版本只写了一个简单的循环当i need n时直接判 -1没有考虑ans 0的情况。在牛客的评测数据里这种边界用例特别多一漏就是一个 Wrong Answer。第三个坑是循环边界的下标问题。i need恰好等于 n 时说明当前这队正好可以把剩下的人全部装完这是合法情况不要误判为无解只有i need n才需要走并入分支。第四个坑是数据范围。n 一般到 10^5 甚至 10^6 级别用 int 完全能扛住队伍数量但如果你不是排序而是用多重循环模拟复杂度很容易飙到 O(n^2)那就直接超时了。我在本地对拍的时候还试过一组很有意思的数据a[2,2,2,1,1,1,1,1]排序后取第一队 (2,2)第二队 (2,1)剩下的 1 们各自成队总共 4 队肉眼看不可能是 3 队或更少。这个用例用来验证贪心是否“拆得太狠”很有效。4. 延伸牛客里那些“长度为3的连续子串”题是同一个思维框架的另一面热搜词里反复出现“长度为3的连续子串”我在牛客题库里确实遇到不少这类题。它们的共同点是给一个字符串或数组要求统计长度固定为 3 的连续子串里满足某个条件的数量。很多第一次刷的人一看到“连续子串”就慌其实窗口长度只有 3根本不需要什么高级滑动窗口优化直接暴力枚举所有长度为 3 的窗口即可。统计的关键在于循环范围是i从 0 到n-3等价于i 3 n写成代码是i 2 n每个窗口就三个下标(i, i1, i2)把条件翻译成三个下标之间的关系就可以 O(n) 完成。比如一个很典型的题统计一个只含 A、B、C 的字符串里有多少个长度为 3 的连续子串满足“三个字符互不相同”。代码如下int countGood(string s) { int n s.size(); int ans 0; for (int i 0; i 2 n; i) { if (s[i] ! s[i1] s[i1] ! s[i2] s[i] ! s[i2]) { ans; } } return ans; }这里最容易错的点有两个一是循环写成i n导致访问s[i2]越界或者把最后两个字符的错误窗口也算进去了二是直接枚举所有子串时把“长度固定为 3”的条件忽略改成双重循环去枚举所有长度平白无故把复杂度提升到 O(n^2)。如果判断条件特别复杂比如“不允许出现 ABA 或 BAB 这种回文模式”可以把每个长度为 3 的子串编码成一个数字用一个预处理的哈希表记录这个数字是否合法然后窗口扫描时直接查表。长度固定为 3 意味着可能的模式最多只有 27 种三字符集下或者 26^3 种字母集下表的大小几乎可以忽略不计。这类题看起来很“小儿科”但牛客的每日一题里经常用它来穿插节奏。它和“乐团派对”看似无关实际上都指向同一个底层能力把一个局部的约束条件准确翻译成代码里的边界判断和条件判断。贪心题错在“想当然地排序”子串题错在“想当然地写循环”本质都是对约束的理解不够精确。5. 用牛客的 tracker 把每日一题坚持成体系光会做一道题是不够的我更想聊聊怎么让刷题变成一个可持续的过程。牛客的题库里有一个“每日一题”的功能每天固定推一道题而 tracker 的核心价值就是把你的刷题行为变成看得见的记录。我自己是这么用 tracker 的。每天中午午休时间花 20 到 30 分钟做当天的每日一题。做完之后不管对错都会在 tracker 里给这道题打一个标签比如“贪心”“DP”“字符串”“图论”。如果错了就额外标一个“错题”标记并顺手记下是卡在思路还是卡在边界条件。每周日晚上我会花十分钟看一下 tracker 的统计数据。当某个标签下的题目正确率明显低于其他标签时就说明这个模块是目前的薄弱点。“乐团派对”这道题就属于典型的贪心标签如果连续几道贪心都栽在边界上那我下周就会刻意补练三四道同类题把“排序方向 剩余并入”这种套路彻底吃透。再分享一个我坚持了很久的小技巧tracker 里的连续打卡天数不要设得太贪。我之前给自己定过“必须每天连续打卡”结果某天出差断了之后动力直线下降。后来改成“一周至少 5 天”心态一下子稳了很多。每日一题的意义不是让你 365 天不中断而是让你始终保持在“每天都动一下脑子”的轨道上。最近我还在 tracker 里给“长度为3的连续子串”这类字符串题单独开了一个标签因为这类题虽然不难但边界问题极其抓人。每次看到热搜词出现相关题目我就知道又有一批人会栽在越界或循环范围上这也是值得反复标记的错题类型。说实话刷题这件事最大的门槛从来不是题目难度而是没有反馈机制。牛客的 tracker 恰好补齐了这一点它让你知道本周练了什么、哪个知识点错得多、连续坚持了多久。有了这些数据每日一题就不再是朋友圈式的打卡表演而是一个真正能帮你查漏补缺的闭环。最后再补充一个实际体验我最近把 tracker 里标记过的所有“贪心”错题统一重刷了一遍“乐团派对”是重刷队列里最典型的一道。重做的时候手比第一次快了很多也终于把“剩余并入”这个分支彻底刻进了脑子里。这种从“错得莫名其妙”到“一眼看穿套路”的变化正是 tracker 每日一题这个组合最让我满意的地方。