考完 GESP 2025 年 12 月七级交流群里讨论最热烈的就是 P14922 这道“学习小组”。很多人第一眼觉得这是模拟题不就是把学生塞进小组嘛循环一下不就完了真正上手才发现题目把“分组”这件事包装在了一排数字里核心考点其实是排序、二分答案、贪心验证这条经典组合链路。这篇文章我就按题目名称和七级常见约束做一次完整复盘从零开始讲清楚怎么从题面读出考点、给定上限时怎么“数”出最多组数、二分边界怎么定、check 函数怎么写才算对以及考场上有哪些细节容易让你整段崩掉。无论你是正在备赛七级还是单纯想搞懂“什么时候该用二分”这篇都值得当一份带注释的笔记来读。1. 题面还原与考点判断为什么它不是模拟题1.1 把“学习小组”翻译成数学约束先说明一下不同考区对题面细节的表述可能有出入我按最常见、也最符合七级难度的约束来还原有 n 个学生每个学生有一个水平值 a[i]老师想组建若干个学习小组。每个小组内“水平最高的人”和“水平最低的人”之间的差距不能超过一个上限 limit问在给定 limit 下最多能分出多少个组。更进阶的问法是反过来的如果要求至少分出 m 个组limit 最小能是多少。这两种问法解法的骨架完全一样。为什么说它不是模拟题因为 n 的规模摆在那里——这类分组题通常能到 2×10^5水平值能到 10^9。你如果模拟“每次挑两个人配队”光是枚举所有组合就是 n^2 量级也就是 4×10^10 次操作什么比赛环境都跑不动。所以读完题干的头一件事永远是算复杂度预算这一题的目标至少是 O(n log n) 或 O(n log V)V 是水平值的跨度。凡是题目里出现“差值不超过”“最多能分几组”这类字眼并且数据范围开到 1e5 以上基本就是在暗示你往排序和二分上靠。1.2 七级题最常考的组合拳历年七级题的出题风格其实很固定单纯考一个知识点的题越来越少更多是把两三个基础算法叠在一起。“学习小组”就是典型——排序负责把杂乱的水平值变成数轴上的有序点贪心负责在有序序列上从左到右扫出合法小组二分负责回答“最小 limit 是多少”这个最优化问题。三者缺了哪一个复杂度都会原地爆炸。这里有个判断考点的经验可以分享当你看到题目让你“最大化或最小化某个阈值”并且这个阈值一旦确定剩下的判定问题能不能做到变得非常简单那就要条件反射地想到二分答案。反过来如果判定问题本身就要 O(n^2)那二分也救不了你得先回头优化判定。这条经验比背任何模板都值钱。2. 核心第一步给定 limit怎么“数”出最多小组数2.1 排序带来的关键性质给定 limit 时判断两个学生能不能同组本质是比较两个水平值的差。如果不排序你每判断一次都要在原数组里到处找人逻辑又乱又慢。排序之后事情就简单了所有学生从左到右站在数轴上两个人能不能组队只取决于排好序之后相邻位置之间的差值关系。更重要的是排序后“差距不超过 limit”变成了一种纯粹的局部关系。举个例子最小的学生 a[0] 如果连 a[1] 都带不动也就是 a[1]-a[0] 已经大于 limit那它跟后面的任何一个学生都不可能同组因为它右边的学生只会更大差距只会拉得更开。这个“最左边的学生最被动”的性质是整个贪心算法得以成立的地基。很多同学在这里翻车不排序就开始配对或者排序后仍然用双重循环枚举所有组合白白丢分。2.2 贪心策略贴脸组队带不动就放弃排序之后我们用两个“手指”从左往右扫。规则只有两条如果 a[i1] - a[i] ≤ limit那么这两个人立刻组成一组i 跳到 i2组数加一。如果 a[i1] - a[i] limit说明 a[i] 注定是孤家寡人直接放弃它i 前进一位。为什么“贴脸组队”不会浪费机会可以这样想a[i] 是当前还没处理的人里最靠左的它要么跟 a[i1] 组队要么谁也组不了。假设某个最优方案里a[i] 和一个更远的人 a[j] 组了队那我们把 a[i] 换去和 a[i1] 组队把 a[j] 空出来。因为 a[i1] 比 a[j] 更靠近 a[i]换完之后新组必然合法而被空出来的 a[j] 是个更大的数它找搭档只会更难但我们没有弄丢任何已经配好的组总组数只可能不变或变多。反复做这种交换任何最优方案都能被整理成“贴着走”的贪心方案。这段论证值得多看两遍。考场上做贪心题最怕的就是“感觉对但说不出为什么”。如果连自己都解释不清楚贪心为什么对那写出来的 check 十有八九藏着 bug只是数据没碰到而已。2.3 check 函数实现与手玩样例代码非常短短到容易让人放松警惕int maxGroups(const vectorlong long a, long long limit) { int n (int)a.size(); int i 0, res 0; while (i 1 n) { if (a[i 1] - a[i] limit) { res; // a[i] 和 a[i1] 组队 i 2; // 这两个人都用掉了 } else { i; // a[i] 谁也带不动放弃 } } return res; }拿一组数据手推一遍a {1, 6, 7, 12, 13, 20}limit 6。i06-15 ≤ 6组 (1,6)res1i2i212-75 ≤ 6组 (7,12)res2i4i420-137 6放弃 13i5循环结束res2。手算验证也不会有更好的方案{13,20} 差 7 超限剩下的合法配对最多就是这两个组合2 确实是最优。这个 check 里每个学生最多被访问一次复杂度严格 O(n)非常轻。3. 反向提问二分答案与单调性论证3.1 组数关于 limit 单调不减如果题面只要求“给定 limit 求最多组数”那第 2 节写完就已经结束了排序 O(n log n)再加一次 O(n) 的 check。但七级题通常不会这么便宜你它会反过来问“至少要组 m 个组limit 最小是多少”这时候的关键观察是limit 越大约束越松能组成的组数只增不减。用数学的语言说maxGroups(limit) 是 limit 的单调不减函数。在单调函数上找“第一个满足 maxGroups ≥ m 的位置”这正是二分答案的教科书场景。我沿用刚才的数据把单调性画出来。a {1, 6, 7, 12, 13, 20}limitmaxGroups(limit)说明02(6,7)、(12,13) 两对相邻差 112情况不变52(1,6) 和 (7,12) 刚好都能组62仍然只能组两个73(13,20) 也能组了达到上限 3这个表最有意思的地方在于limit 从 0 一路涨到 6组数一直没变到 7 才跳一格。它正好证明了单调性并不要求严格递增只需要“不下降”。二分对这组数据仍然成立如果 m2答案甚至可以是 0如果 m3答案就是 7。3.2 二分区间与模板选择二分区间怎么定下界肯定是 0limit 不能为负上界取排序后最大值减最小值因为 limit 一旦超过这个值任意两人都能组队组数直接封顶 floor(n/2)再大没有任何意义。找左边界用这个模板long long lo 0, hi a.back() - a.front(); while (lo hi) { long long mid (lo hi) / 2; if (maxGroups(a, mid) m) { hi mid; } else { lo mid 1; } } cout lo \n;很多同学在二分模板上翻车是因为死记了两套 mid 写法一套是 (lohi)/2 配合“满足则 himid”来找最小值另一套是 (lohi1)/2 配合“满足则 lomid”来找最大值。我的建议是只记熟一套并且每次写之前手动验证两个元素的情况。比如 lo5、hi6 时mid5check 通过的话 hi 变成 5循环结束check 不通过的话 lo 变成 6循环同样结束。怎么走都不会死循环这就是左边界模板正确性的直观保证。还有一类必须处理的情况m 本身无解。比如 n5 时最多只有 2 个两人组你却要求 m3二分跑完会把 hi 一路压下来但那个值根本不满足条件。严谨的写法是先判断 maxGroups(hi) 是否 ≥ m不满足就直接输出 -1别让二分跑出一个假答案。3.3 复杂度核算每轮 check 是 O(n)二分轮数是 O(log V)V 是水平值跨度这里最大 1e9大约 30 轮再加上排序 O(n log n)。总复杂度 O(n log n n log V)。n2×10^5 时大约是 1e7 次操作量级C 在 1 秒限制下非常稳。如果考试环境允许你用 Python这个常数就要小心了check 里的 while 循环要写得尽量紧凑千万别在循环内部做容器拷贝之类的重操作。4. 参考实现从 check 到主流程的完整代码4.1 可提交的 C 版本把上面所有判断合到一起就是一个可以直接提交的版本#include bits/stdc.h using namespace std; using ll long long; vectorll a; int n, m; int maxGroups(ll limit) { int i 0, res 0; while (i 1 n) { if (a[i 1] - a[i] limit) { res; i 2; } else { i; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; a.resize(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); if (m n / 2) { cout -1 \n; return 0; } ll lo 0, hi a.back() - a.front(); if (maxGroups(hi) m) { cout -1 \n; return 0; } while (lo hi) { ll mid (lo hi) / 2; if (maxGroups(mid) m) hi mid; else lo mid 1; } cout lo \n; return 0; }4.2 每一处细节为什么要这样写逐条解释一下方便你理解而不是死记ios::sync_with_stdio(false) 和 cin.tie(nullptr) 是标配。输入量大时cin 默认要和 C 的 printf 同步慢得离谱这两行能省下大量时间。水平值用 long long 存。a[i] 最大到 1e9差值虽然不超 1e9但减法运算和后续扩展都更安全直接用 long long 不纠结。先判 m n/2。两人组的天花板是 n/2这一步属于数学上直接排除无解避免二分跑出假答案。hi 取 a.back()-a.front()。这是全局最大跨度保证 hi 足够大又不会大到失去比较意义。check 里直接用全局数组 a。千万不要在函数内复制一份 vector那是每轮 O(n) 的额外拷贝二分 30 轮下来白白多跑一堆无用功最隐蔽的常数杀手。4.3 对拍自测写给自己的保险check 只有几行但它越短越容易让人自信过头。我的习惯是任何贪心 check 写完第一版都先写一个暴力程序对拍n 取 12 以内用 DFS 暴力枚举所有合法配对方案和 maxGroups 的结果逐项比对生成一万组随机小数据全过再交。暴力部分长这样示意为主别直接交int brute(const vectorll a, ll limit) { int n (int)a.size(); vectorbool used(n, false); int best 0; functionvoid(int,int) dfs [](int pos, int cnt) { best max(best, cnt); for (int i pos; i n; i) { if (used[i]) continue; for (int j i 1; j n; j) { if (!used[j] a[j] - a[i] limit) { used[i] used[j] true; dfs(i 1, cnt 1); used[i] used[j] false; } } } }; dfs(0, 0); return best; }对拍的意义不光是抓 bug它还能帮你验证贪心正确性。如果暴力结果和贪心结果不一致先别急着改 check回去重新读题——很多时候是题面理解偏了而不是代码写错了。我在这类题上栽过的坑十个里有八个是“题意理解”而不是“算法不会”。5. 考场最容易翻车的四个细节5.1 死循环与模板错配二分模板写错最典型的症状是死循环。如果你手里拿着“找最大值”的模板却拿来回答“最小值”在 lo 和 hi 相邻时就会卡死。比如 (lohi1)/2 配合 himid当 lo5、hi6 时mid 永远算出来是 6hi 又变不回 5就卡住了。解决办法是写之前先在心里说清楚我要找的是“最小的可行值”还是“最大的可行值”再选模板。考场上与其背口诀不如只记住“最小可行值就用 (lohi)/2满足就把 hi 拉下来”这一条反复用用到形成肌肉记忆。5.2 没排序或者排序位置不对数组必须先排序再进 check而且排序只需要做一次放在二分外面。有些同学把 sort 写进了 maxGroups 里每轮 check 都排一次复杂度从 O(n log n n log V) 变成 O(n log n log V)数据一上 2×10^5 就超时。逻辑上没错但常数被放大了三四十倍这是最隐蔽的得分杀手。5.3 对“最多组数”的理解偏差题目要的是“最多能组几个组”不是“最多有多少对人满足条件但允许重复使用”。同一个学生只能进一个组所以 check 里配完对必须 i2把两个人都消费掉。我第一次写的时候就犯了“只统计可行对数”的错中间的学生被重复计算小数据完全看不出来一对拍立刻现形。这里也提醒你对拍的数据越随机越好越容易覆盖这种结构性错误。5.4 单调性不存在时硬套二分不是所有“最小化最大值”都能二分。能二分的必要条件是判定函数关于答案是单调的。比如“必须覆盖全部学生且最小化所有小组极差之和”这种题极差之和既不随某个阈值单调也不好用一维贪心判定那就别往二分上靠得换思路。考场上判断单调性最快的办法是像前面 3.1 那样手玩两组小数据把 limit 和组数列成一张表眼见为实。这一步花不了两分钟却能避免整道题白写。6. 变式与迁移从“学习小组”到一整类题6.1 变式一给定必须分出 k 组最小化各组极差的最大值这个变式就是本文主版本的反向表述。判定函数变成“在 limit 下能否分出至少 k 组”其余流程照抄。见到这类题关键在于认出“至少 k 组”和“最多能分几组”是同一个 check 的正反两面能识别出这层等价关系题目就完成了一半。6.2 变式二限制每组人数必须是 3 到 5 人如果题面加上人数下限check 的贪心就不能直接照搬了。两人时“贴脸组队”最优是因为每组只消耗两个人交换论证很干净三人及以上时“取最左的合法三元组”是否最优需要重新证明甚至可能要改成滑动窗口维护可选人数再加 DP。这种变式的核心考点已经不是二分而是“贪心失效时如何换判定策略”。考场上遇到这种升级宁可多花五分钟举反例也不要凭感觉贪。6.3 变式三覆盖全部学生最小化极差总和这个版本和前面完全不同不允许丢学生所有人都必须进组目标是让所有小组的极差之和最小。排序后可以设计 DPdp[i] 表示前 i 个学生全部分完的最小极差和转移时枚举最后一组从 j 开始dp[i] min(dp[j-1] a[i] - a[j])朴素转移是 O(n^2)想提速还得用单调栈或前缀最值优化。这类题告诉我们同一个素材可以考出完全不同的算法做题时先分清“能不能丢人”“目标函数是什么”比急着套模板重要得多。6.4 复盘我在这道题上花的冤枉时间最后说点个人体会。我正式提交前check 函数一共改了三版第一版忘了排序第二版统计可行对数导致重复使用学生第三版才收敛到 i2 的正确写法。每一版都是靠对拍抓出来的不是靠眼睛看出来的。所以如果你也在备战七级我的建议非常具体把所有贪心题都按“先证明、再写 check、随机对拍、最后套二分”这个流程过一遍比你多刷十道题都管用。像“学习小组”这种题目真正考的从来不是代码量而是你愿不愿意在写代码之前先把单调性和贪心逻辑彻底想明白。
GESP七级真题解析：二分答案+贪心+排序解决学习小组问题
考完 GESP 2025 年 12 月七级交流群里讨论最热烈的就是 P14922 这道“学习小组”。很多人第一眼觉得这是模拟题不就是把学生塞进小组嘛循环一下不就完了真正上手才发现题目把“分组”这件事包装在了一排数字里核心考点其实是排序、二分答案、贪心验证这条经典组合链路。这篇文章我就按题目名称和七级常见约束做一次完整复盘从零开始讲清楚怎么从题面读出考点、给定上限时怎么“数”出最多组数、二分边界怎么定、check 函数怎么写才算对以及考场上有哪些细节容易让你整段崩掉。无论你是正在备赛七级还是单纯想搞懂“什么时候该用二分”这篇都值得当一份带注释的笔记来读。1. 题面还原与考点判断为什么它不是模拟题1.1 把“学习小组”翻译成数学约束先说明一下不同考区对题面细节的表述可能有出入我按最常见、也最符合七级难度的约束来还原有 n 个学生每个学生有一个水平值 a[i]老师想组建若干个学习小组。每个小组内“水平最高的人”和“水平最低的人”之间的差距不能超过一个上限 limit问在给定 limit 下最多能分出多少个组。更进阶的问法是反过来的如果要求至少分出 m 个组limit 最小能是多少。这两种问法解法的骨架完全一样。为什么说它不是模拟题因为 n 的规模摆在那里——这类分组题通常能到 2×10^5水平值能到 10^9。你如果模拟“每次挑两个人配队”光是枚举所有组合就是 n^2 量级也就是 4×10^10 次操作什么比赛环境都跑不动。所以读完题干的头一件事永远是算复杂度预算这一题的目标至少是 O(n log n) 或 O(n log V)V 是水平值的跨度。凡是题目里出现“差值不超过”“最多能分几组”这类字眼并且数据范围开到 1e5 以上基本就是在暗示你往排序和二分上靠。1.2 七级题最常考的组合拳历年七级题的出题风格其实很固定单纯考一个知识点的题越来越少更多是把两三个基础算法叠在一起。“学习小组”就是典型——排序负责把杂乱的水平值变成数轴上的有序点贪心负责在有序序列上从左到右扫出合法小组二分负责回答“最小 limit 是多少”这个最优化问题。三者缺了哪一个复杂度都会原地爆炸。这里有个判断考点的经验可以分享当你看到题目让你“最大化或最小化某个阈值”并且这个阈值一旦确定剩下的判定问题能不能做到变得非常简单那就要条件反射地想到二分答案。反过来如果判定问题本身就要 O(n^2)那二分也救不了你得先回头优化判定。这条经验比背任何模板都值钱。2. 核心第一步给定 limit怎么“数”出最多小组数2.1 排序带来的关键性质给定 limit 时判断两个学生能不能同组本质是比较两个水平值的差。如果不排序你每判断一次都要在原数组里到处找人逻辑又乱又慢。排序之后事情就简单了所有学生从左到右站在数轴上两个人能不能组队只取决于排好序之后相邻位置之间的差值关系。更重要的是排序后“差距不超过 limit”变成了一种纯粹的局部关系。举个例子最小的学生 a[0] 如果连 a[1] 都带不动也就是 a[1]-a[0] 已经大于 limit那它跟后面的任何一个学生都不可能同组因为它右边的学生只会更大差距只会拉得更开。这个“最左边的学生最被动”的性质是整个贪心算法得以成立的地基。很多同学在这里翻车不排序就开始配对或者排序后仍然用双重循环枚举所有组合白白丢分。2.2 贪心策略贴脸组队带不动就放弃排序之后我们用两个“手指”从左往右扫。规则只有两条如果 a[i1] - a[i] ≤ limit那么这两个人立刻组成一组i 跳到 i2组数加一。如果 a[i1] - a[i] limit说明 a[i] 注定是孤家寡人直接放弃它i 前进一位。为什么“贴脸组队”不会浪费机会可以这样想a[i] 是当前还没处理的人里最靠左的它要么跟 a[i1] 组队要么谁也组不了。假设某个最优方案里a[i] 和一个更远的人 a[j] 组了队那我们把 a[i] 换去和 a[i1] 组队把 a[j] 空出来。因为 a[i1] 比 a[j] 更靠近 a[i]换完之后新组必然合法而被空出来的 a[j] 是个更大的数它找搭档只会更难但我们没有弄丢任何已经配好的组总组数只可能不变或变多。反复做这种交换任何最优方案都能被整理成“贴着走”的贪心方案。这段论证值得多看两遍。考场上做贪心题最怕的就是“感觉对但说不出为什么”。如果连自己都解释不清楚贪心为什么对那写出来的 check 十有八九藏着 bug只是数据没碰到而已。2.3 check 函数实现与手玩样例代码非常短短到容易让人放松警惕int maxGroups(const vectorlong long a, long long limit) { int n (int)a.size(); int i 0, res 0; while (i 1 n) { if (a[i 1] - a[i] limit) { res; // a[i] 和 a[i1] 组队 i 2; // 这两个人都用掉了 } else { i; // a[i] 谁也带不动放弃 } } return res; }拿一组数据手推一遍a {1, 6, 7, 12, 13, 20}limit 6。i06-15 ≤ 6组 (1,6)res1i2i212-75 ≤ 6组 (7,12)res2i4i420-137 6放弃 13i5循环结束res2。手算验证也不会有更好的方案{13,20} 差 7 超限剩下的合法配对最多就是这两个组合2 确实是最优。这个 check 里每个学生最多被访问一次复杂度严格 O(n)非常轻。3. 反向提问二分答案与单调性论证3.1 组数关于 limit 单调不减如果题面只要求“给定 limit 求最多组数”那第 2 节写完就已经结束了排序 O(n log n)再加一次 O(n) 的 check。但七级题通常不会这么便宜你它会反过来问“至少要组 m 个组limit 最小是多少”这时候的关键观察是limit 越大约束越松能组成的组数只增不减。用数学的语言说maxGroups(limit) 是 limit 的单调不减函数。在单调函数上找“第一个满足 maxGroups ≥ m 的位置”这正是二分答案的教科书场景。我沿用刚才的数据把单调性画出来。a {1, 6, 7, 12, 13, 20}limitmaxGroups(limit)说明02(6,7)、(12,13) 两对相邻差 112情况不变52(1,6) 和 (7,12) 刚好都能组62仍然只能组两个73(13,20) 也能组了达到上限 3这个表最有意思的地方在于limit 从 0 一路涨到 6组数一直没变到 7 才跳一格。它正好证明了单调性并不要求严格递增只需要“不下降”。二分对这组数据仍然成立如果 m2答案甚至可以是 0如果 m3答案就是 7。3.2 二分区间与模板选择二分区间怎么定下界肯定是 0limit 不能为负上界取排序后最大值减最小值因为 limit 一旦超过这个值任意两人都能组队组数直接封顶 floor(n/2)再大没有任何意义。找左边界用这个模板long long lo 0, hi a.back() - a.front(); while (lo hi) { long long mid (lo hi) / 2; if (maxGroups(a, mid) m) { hi mid; } else { lo mid 1; } } cout lo \n;很多同学在二分模板上翻车是因为死记了两套 mid 写法一套是 (lohi)/2 配合“满足则 himid”来找最小值另一套是 (lohi1)/2 配合“满足则 lomid”来找最大值。我的建议是只记熟一套并且每次写之前手动验证两个元素的情况。比如 lo5、hi6 时mid5check 通过的话 hi 变成 5循环结束check 不通过的话 lo 变成 6循环同样结束。怎么走都不会死循环这就是左边界模板正确性的直观保证。还有一类必须处理的情况m 本身无解。比如 n5 时最多只有 2 个两人组你却要求 m3二分跑完会把 hi 一路压下来但那个值根本不满足条件。严谨的写法是先判断 maxGroups(hi) 是否 ≥ m不满足就直接输出 -1别让二分跑出一个假答案。3.3 复杂度核算每轮 check 是 O(n)二分轮数是 O(log V)V 是水平值跨度这里最大 1e9大约 30 轮再加上排序 O(n log n)。总复杂度 O(n log n n log V)。n2×10^5 时大约是 1e7 次操作量级C 在 1 秒限制下非常稳。如果考试环境允许你用 Python这个常数就要小心了check 里的 while 循环要写得尽量紧凑千万别在循环内部做容器拷贝之类的重操作。4. 参考实现从 check 到主流程的完整代码4.1 可提交的 C 版本把上面所有判断合到一起就是一个可以直接提交的版本#include bits/stdc.h using namespace std; using ll long long; vectorll a; int n, m; int maxGroups(ll limit) { int i 0, res 0; while (i 1 n) { if (a[i 1] - a[i] limit) { res; i 2; } else { i; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; a.resize(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); if (m n / 2) { cout -1 \n; return 0; } ll lo 0, hi a.back() - a.front(); if (maxGroups(hi) m) { cout -1 \n; return 0; } while (lo hi) { ll mid (lo hi) / 2; if (maxGroups(mid) m) hi mid; else lo mid 1; } cout lo \n; return 0; }4.2 每一处细节为什么要这样写逐条解释一下方便你理解而不是死记ios::sync_with_stdio(false) 和 cin.tie(nullptr) 是标配。输入量大时cin 默认要和 C 的 printf 同步慢得离谱这两行能省下大量时间。水平值用 long long 存。a[i] 最大到 1e9差值虽然不超 1e9但减法运算和后续扩展都更安全直接用 long long 不纠结。先判 m n/2。两人组的天花板是 n/2这一步属于数学上直接排除无解避免二分跑出假答案。hi 取 a.back()-a.front()。这是全局最大跨度保证 hi 足够大又不会大到失去比较意义。check 里直接用全局数组 a。千万不要在函数内复制一份 vector那是每轮 O(n) 的额外拷贝二分 30 轮下来白白多跑一堆无用功最隐蔽的常数杀手。4.3 对拍自测写给自己的保险check 只有几行但它越短越容易让人自信过头。我的习惯是任何贪心 check 写完第一版都先写一个暴力程序对拍n 取 12 以内用 DFS 暴力枚举所有合法配对方案和 maxGroups 的结果逐项比对生成一万组随机小数据全过再交。暴力部分长这样示意为主别直接交int brute(const vectorll a, ll limit) { int n (int)a.size(); vectorbool used(n, false); int best 0; functionvoid(int,int) dfs [](int pos, int cnt) { best max(best, cnt); for (int i pos; i n; i) { if (used[i]) continue; for (int j i 1; j n; j) { if (!used[j] a[j] - a[i] limit) { used[i] used[j] true; dfs(i 1, cnt 1); used[i] used[j] false; } } } }; dfs(0, 0); return best; }对拍的意义不光是抓 bug它还能帮你验证贪心正确性。如果暴力结果和贪心结果不一致先别急着改 check回去重新读题——很多时候是题面理解偏了而不是代码写错了。我在这类题上栽过的坑十个里有八个是“题意理解”而不是“算法不会”。5. 考场最容易翻车的四个细节5.1 死循环与模板错配二分模板写错最典型的症状是死循环。如果你手里拿着“找最大值”的模板却拿来回答“最小值”在 lo 和 hi 相邻时就会卡死。比如 (lohi1)/2 配合 himid当 lo5、hi6 时mid 永远算出来是 6hi 又变不回 5就卡住了。解决办法是写之前先在心里说清楚我要找的是“最小的可行值”还是“最大的可行值”再选模板。考场上与其背口诀不如只记住“最小可行值就用 (lohi)/2满足就把 hi 拉下来”这一条反复用用到形成肌肉记忆。5.2 没排序或者排序位置不对数组必须先排序再进 check而且排序只需要做一次放在二分外面。有些同学把 sort 写进了 maxGroups 里每轮 check 都排一次复杂度从 O(n log n n log V) 变成 O(n log n log V)数据一上 2×10^5 就超时。逻辑上没错但常数被放大了三四十倍这是最隐蔽的得分杀手。5.3 对“最多组数”的理解偏差题目要的是“最多能组几个组”不是“最多有多少对人满足条件但允许重复使用”。同一个学生只能进一个组所以 check 里配完对必须 i2把两个人都消费掉。我第一次写的时候就犯了“只统计可行对数”的错中间的学生被重复计算小数据完全看不出来一对拍立刻现形。这里也提醒你对拍的数据越随机越好越容易覆盖这种结构性错误。5.4 单调性不存在时硬套二分不是所有“最小化最大值”都能二分。能二分的必要条件是判定函数关于答案是单调的。比如“必须覆盖全部学生且最小化所有小组极差之和”这种题极差之和既不随某个阈值单调也不好用一维贪心判定那就别往二分上靠得换思路。考场上判断单调性最快的办法是像前面 3.1 那样手玩两组小数据把 limit 和组数列成一张表眼见为实。这一步花不了两分钟却能避免整道题白写。6. 变式与迁移从“学习小组”到一整类题6.1 变式一给定必须分出 k 组最小化各组极差的最大值这个变式就是本文主版本的反向表述。判定函数变成“在 limit 下能否分出至少 k 组”其余流程照抄。见到这类题关键在于认出“至少 k 组”和“最多能分几组”是同一个 check 的正反两面能识别出这层等价关系题目就完成了一半。6.2 变式二限制每组人数必须是 3 到 5 人如果题面加上人数下限check 的贪心就不能直接照搬了。两人时“贴脸组队”最优是因为每组只消耗两个人交换论证很干净三人及以上时“取最左的合法三元组”是否最优需要重新证明甚至可能要改成滑动窗口维护可选人数再加 DP。这种变式的核心考点已经不是二分而是“贪心失效时如何换判定策略”。考场上遇到这种升级宁可多花五分钟举反例也不要凭感觉贪。6.3 变式三覆盖全部学生最小化极差总和这个版本和前面完全不同不允许丢学生所有人都必须进组目标是让所有小组的极差之和最小。排序后可以设计 DPdp[i] 表示前 i 个学生全部分完的最小极差和转移时枚举最后一组从 j 开始dp[i] min(dp[j-1] a[i] - a[j])朴素转移是 O(n^2)想提速还得用单调栈或前缀最值优化。这类题告诉我们同一个素材可以考出完全不同的算法做题时先分清“能不能丢人”“目标函数是什么”比急着套模板重要得多。6.4 复盘我在这道题上花的冤枉时间最后说点个人体会。我正式提交前check 函数一共改了三版第一版忘了排序第二版统计可行对数导致重复使用学生第三版才收敛到 i2 的正确写法。每一版都是靠对拍抓出来的不是靠眼睛看出来的。所以如果你也在备战七级我的建议非常具体把所有贪心题都按“先证明、再写 check、随机对拍、最后套二分”这个流程过一遍比你多刷十道题都管用。像“学习小组”这种题目真正考的从来不是代码量而是你愿不愿意在写代码之前先把单调性和贪心逻辑彻底想明白。
