1. 考场初见这道题在整套七级卷子里是什么位置1.1 我的第一反应2025年12月那场GESP C七级考试我做完选择、判断和前面几道程序题后翻到程序设计大题第一眼看到学习小组这个题目时心里先松了一口气——看起来不复杂。但读完题面我在草稿纸上画了快二十分钟才意识到这是一道典型的序列切分型动态规划并且它同时牵涉排序、区间合法性判断、区间最小值维护三个环节。考后和认识的同学对答案至少有两个人因为不同原因在这题上失分一个是上来就按从小到大贪心分组样例过了大数据一跑就错另一个想到了用动态规划却漏掉了每组人数不得少于 k 人的约束转移方程写得半对半错。这篇复盘就把这道题的回忆版题意、完整推导过程和 C 题解整理出来。如果你计划备考 2026 年 3 月或 6 月的 GESP 七级认证这道题值得当作备考样板反复刷。1.2 它为什么能拉开差距从 GESP 七级考纲来看重点覆盖树与图的遍历、最短路、最小生成树、基础动态规划、二分答案等方向。学习小组表面上是一个分组模拟题实际落点却是动态规划而且是七级里很容易被轻视的分段 DP 方向。它不像树形 DP 那样有明显递归结构也不像背包那样有固定模板很多人的第一反应是能不能贪心这恰恰是题目设计得比较巧妙的地方样例数据会引导你往贪心想但真正的数据范围会告诉你贪心站不住脚。整套卷子做下来我的感受是这道题给的时间压力不小前四十分钟如果沉浸在图论题里到这里就容易失去耐心。可一旦看穿它排序后切成若干连续段的本质代码量并不多。它考的不是背模板而是现场建模能力。下面我从回忆版题意说起逐步给出推导和实现。2. 回忆版题意分组条件与输入输出格式2.1 记忆中的题面说明一下GESP 官方不会在考后马上释放完整真题所以下面这份题面是根据同场考生的回忆和我的考场印象整理出来的复现版核心流程和考点保持原样具体表述、样例数值可能和官方卷面有差异。刷题时以这个复现版为准思路是一致的。题目大意如下老师要把班里的 n 名学生分成若干个学习小组。每个学生有一个能力值 a[i]。老师规定每个小组至少有 k 名学生同一小组内能力值最高和最低的学生差距不能超过 d。求最少能分成多少个小组使得所有学生都恰好被分到某一个小组中。如果无法完成分组输出 -1。输入格式第一行三个整数 n、k、d第二行 n 个整数 a[1..n]。输出格式一个整数表示最少小组数若无法分组则输出 -1。2.2 数据范围与时间限制虽然官方卷面给出的数据范围我记不太准确但按七级程序设计题的通常强度大致可以按以下范围来约束参数取值说明n1 ~ 2×10^5学生人数规模要到 O(n log n) 以内k1 ~ n每组最少人数d0 ~ 10^9能力差距上限a[i]0 ~ 10^9能力值记得用 long long 读这个数据范围直接排除了 O(n^2) 的暴力分组方案。也就是说正确解法的排序部分应该是 O(n log n)分组计算部分至少要压到 O(n log n)最好是 O(n)。2.3 考点定位我在考场上把它定位成三个步骤的叠加排序先按能力值升序排序连续段建模把任意分组转化为把排序后的数组切成若干连续段动态规划求最少段数每段需要满足长度 ≥ k且首尾能力差 ≤ d。这个定位过程就是解这道题的核心下面一节详细展开。3. 解题的第一步为什么排序之后分组只可能是连续段3.1 交换论证先排序再切分一定不亏很多同学看到分组两个字第一反应是组合数爆炸n 个学生任意分组方案数根本枚举不完。但题目里组内能力极差不能超过 d这个条件给了强结构。先说结论一定存在一个最优解使得每个小组在按能力值升序排序之后都是数组里的一段连续区间。换句话说不需要考虑跨段取人的分组。为什么可以用一个非常朴素的交换论证来解释。假设排序后的数组是 b[1] ≤ b[2] ≤ ... ≤ b[n]。任意取一个最优分组方案把某个小组的学生下标标出来。如果这个小组中有两个学生 b[x] 和 b[y]而且 x y同时他们之间漏掉了一个下标 zx z y而这个 b[z] 被分到了其他组那么我就可以把 b[z] 拿进这个小组再从当前小组里挑一个与它交换的成员送出去。因为数组是升序的把中间值放回当前组的极差约束时组内 max 不会变大min 不会变小所以极差只会更小而被换出去的那个学生到另一个组里也不一定破坏约束因为它的能力值正好处在两个值的中间地带属于两头都套得上的位置。反复进行这种交换最终所有小组的成员下标都会变成连续区间。用生活类比就像排队取餐能力值从小到大排列如果一组人里面夹着另一个组的人那这两组的成员范围必然交错。既然约束只关心区间内的最大最小差距那么把夹在中间的人归到同一组只会有利于满足极差限制。这个结论是整个解法的地基。3.2 贪心行不行反例说明贪心为什么错排序后切连续段这个结论一出最容易想到的就是贪心从左往右扫遇到能成一组就切一组。有经验的选手会立刻警惕因为切分长度还要受到至少 k 人的约束这往往就是贪心失灵的地方。看一个反例n9k2d3 a [1, 2, 3, 4, 5, 6, 7, 8, 9]如果贪心每段尽量短就会切成 [1,2]、[3,4]、[5,6]、[7,8]最后剩下一个 9长度不足 k直接认为无解输出 -1。但实际上 [1,2,3]、[4,5,6]、[7,8,9] 就是合法且最优的 3 组。所以最短合法段贪心是错的。那每段尽量长呢这个例子用最长段贪心恰好能得到 3 组看起来可行但很容易构造反例。比如n7k3d4 a [1, 2, 5, 6, 9, 10, 13]最长段贪心从 1 开始取1 到 5 极差 4满足但再往后加 6 极差变成 5于是切出 [1,2,5]剩下 [6,9,10,13]从 6 开始最长能取到 9极差 3切 [6,9]最后剩 [10,13] 长度只有 2不够 3输出无解。但手动看[1,2,5]、[6,9,10,13] 这段极差是 7不行改成 [1,2,5,6] 极差 5也不行实际上这个数据在 k3、d4 下真的无解所以这个反例不够有力。我需要强调最长段贪心不是错误在无解上而是错误在少数情况下能把人分完但分的组数不一定最少。不过为了行文严谨我建议反问一句——就算最长段贪心碰巧能把人分完你能证明它得到的组数一定最少吗如果不能考试时就不该拿没证明的贪心去赌。这也是为什么正确做法必须退回到动态规划用一个可以严格证明的状态转移把所有切分方案都覆盖到。4. 状态设计与转移方程序列切分DP的完整推导4.1 dp[i] 的定义和转移式排序之后问题变成给定升序数组 a[1..n]把它切成若干连续段每段长度 ≥ k且每段首尾差值 ≤ d求最少段数。设 dp[i] 表示把前 i 个学生即 a[1..i]全部完成分组所需的最少小组数。边界条件是 dp[0]0表示前 0 个学生不需要分组。考虑最后一段是从第 j1 个学生到第 i 个学生那么显然要满足两个条件段长度至少为 ki - j ≥ k也就是 j ≤ i - k段内极差不超过 da[i] - a[j1] ≤ d也就是 a[j1] ≥ a[i] - d。于是转移方程写出来就是dp[i] 1 min { dp[j] }其中 j 必须落在合法区间内。这个合法区间的左右端点可以明确算出来。令 R i - k这是 j 的上界表示最后一段至少要留 k 个人。令 threshold a[i] - d这是最后一段第一位学生能力值的下限。由于数组升序我可以二分找到第一个大于等于 threshold 的位置 lb那么 j1 ≥ lb即 j ≥ lb - 1。同时 j 不能小于 0所以左端点 L max(0, lb - 1)。因此转移区间就是j ∈ [ L, R ]只要 L ≤ R并且这个区间里存在一个可达的 dp 值dp[i] 就能由它更新过来。4.2 这个式子怎么高效求 min dp[j]暴力做法是每次枚举 j复杂度 O(n^2)在 n2×10^5 下直接超时。需要优化的点很明确左侧 L 和右侧 R 都随 i 单调不减。R i - k 显然随 i 增大而增大threshold a[i] - d 因为数组升序也随 i 增大而增大所以 lower_bound 得到的 lb 不会往左移动L 也不会减少。既然窗口两端都是单调的就有两条路可走方案数据结构复杂度特点方案一线段树维护 dp 区间最小值O(n log n)思路直白容错高方案二单调队列维护窗口内最小 dpO(n)代码短但要理解单调性我个人建议考场先写方案一确保不丢分有时间再优化成方案二。下面两版代码都给出。4.3 为什么 j 区间 必须同时满足两个条件这里最容易漏掉的是很多选手会记得段长条件 j ≤ i-k却忘了还有极差条件。反过来也有选手只算极差忽略了段长。这两个条件任何一个不满足转移都是非法的。我从两个角度检查自己如果 j 太靠左说明最后一段包括了很多学生段长当然足够但极差可能爆掉a[i] - a[j1] d不满足题意如果 j 太靠右说明最后一段人太少可能不足 k 个也不合法。所以合法 j 必须落在左端点 L 和右端点 R的夹缝里。这个夹缝的推导既是本题的题眼也是我考场上想了最久的地方。5. C 题解线段树版与单调队列版5.1 先写一版不容易错的线段树维护区间最小值线段树版本思路最直接每次算出 L 和 R 后在线段树上查询区间 [L, R] 的 dp 最小值再用它更新 dp[i]并把 dp[i] 插入线段树位置 i。这样每一步都清清楚楚适合在考场上稳扎稳打。#include bits/stdc.h using namespace std; const int INF 1e9; vectorint seg; void update(int node, int l, int r, int pos, int val) { if (l r) { seg[node] val; return; } int mid (l r) 1; if (pos mid) update(node 1, l, mid, pos, val); else update(node 1 | 1, mid 1, r, pos, val); seg[node] min(seg[node 1], seg[node 1 | 1]); } int query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return seg[node]; int mid (l r) 1; int res INF; if (ql mid) res min(res, query(node 1, l, mid, ql, qr)); if (qr mid) res min(res, query(node 1 | 1, mid 1, r, ql, qr)); return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; long long d; cin n k d; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; sort(a.begin() 1, a.end()); seg.assign(4 * (n 1) 5, INF); vectorint dp(n 1, INF); dp[0] 0; update(1, 0, n, 0, 0); for (int i 1; i n; i) { int R i - k; if (R 0) continue; long long need a[i] - d; int lb lower_bound(a.begin() 1, a.begin() i 1, need) - a.begin(); int L max(0, lb - 1); if (L R) continue; int best query(1, 0, n, L, R); if (best INF) { dp[i] best 1; update(1, 0, n, i, dp[i]); } } cout (dp[n] INF ? -1 : dp[n]) \n; return 0; }这里有个细节lower_bound 的查找范围我写的是a.begin() 1到a.begin() i 1而不是整个数组。原因很简单最后一段的起点 j1 不可能大于 i所以只需要在前 i 个元素里找最小可行起点。写错成全局查找会把 j 算到 i 右边导致非法转移。5.2 更进一步滑动窗口单调队列 O(n) 写法线段树虽然稳但代码量稍大。如果对滑动窗口足够熟可以用单调队列把 DP 部分压到 O(n)。核心思想是维护当前窗口 [L, R] 内所有可行 j 的 dp 值队头永远是窗口内 dp 值最小的那个。#include bits/stdc.h using namespace std; const int INF 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; long long d; cin n k d; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; sort(a.begin() 1, a.end()); vectorint dp(n 1, INF); dp[0] 0; dequeint q; // 存下标 j保证队头 dp 值最小 for (int i 1; i n; i) { int R i - k; if (R 0 dp[R] INF) { while (!q.empty() dp[q.back()] dp[R]) q.pop_back(); q.push_back(R); } long long need a[i] - d; int lb lower_bound(a.begin() 1, a.begin() i 1, need) - a.begin(); int L max(0, lb - 1); while (!q.empty() q.front() L) q.pop_front(); while (!q.empty() q.front() R) q.pop_front(); if (!q.empty()) dp[i] dp[q.front()] 1; } cout (dp[n] INF ? -1 : dp[n]) \n; return 0; }为什么可以这样滑动因为每轮 i 增大时新进入窗口的 j 只有 Ri-k 这一个而且 R 是单调增加的窗口左端点 L 也单调不减。所以所有元素入队一次、出队一次总复杂度 O(n)。排序是 O(n log n)整体瓶颈就在排序上。注意入队时dp[R] INF的判断不能省如果 R 本身不可达把 INF 塞进单调队列会污染队尾单调性后面可能把真实的最小 dp 弹掉。5.3 用一个完整例子手动跑一遍拿前面的例子来验证n9k2d3a[1,2,3,4,5,6,7,8,9]。i1R-1跳过dp[1] 保持 INF即前 1 个人无法单独成组i2R0dp[0]0 入队need-2lb1L0队列里有 0dp[2]1表示前 2 个人分成 1 组i3R1dp[1]INF不入队need0lb1L0队列里仍有 0dp[3]1表示前 3 个人 [1,2,3] 可以成 1 组i4R2dp[2]1 入队need1lb1L0队列中 dp[0]0 最小dp[4]1表示前 4 个人 [1,2,3,4] 极差 31 组就能覆盖i5R3dp[3]1 入队need2lb2a[2]2L1弹出下标 0剩余下标 dp 最小为 1dp[5]2即前 5 个人至少要 2 组i9R7dp[7]2 入队need6lb6L5窗口中 dp 最小为 2dp[9]3。最终输出 3和手动最优方案一致。6. 边界数据、易错点与考场经验6.1 最容易翻车的四个地方第一k1 的边界。k1 表示每组至少一个人这时候所有人都可以被各自分成一组但如果能力极差也满足最好当然是全部一人一组还是合并成一组显然合并更优所以 dp 应该找到跨度更大的合法段。代码里 Ri-1每次新加入的 j 是 i-1滑动窗口逻辑不变。考场最容易在这里栽的是想当然认为每组至少 1 人就是无脑分成 n 组忽略最少小组数的要求。第二d0 的情况。d0 意味着同一组内所有人能力值必须完全相同。排序后要切连续段每个段内部的数值都一样。这种情况 data 中可能存在大量相同值lower_bound 找到的 lb 是第一个等于当前值的位置不会有问题但要注意如果某个值的数量少于 k必然无解。手动构造一个 n6, k3, d0, a[1,1,2,2,3,3]输出就应该是 -1。第三long long 溢出。n、k 是 int 级别但 a[i] 和 d 是 10^9 级别a[i] - d可能是负数也可能超过 int 范围。我见过有人用 int 存差值导致负数溢出判错。稳妥做法是 a 数组、d、threshold 全部声明 long long。第四lower_bound 的终点写错。前面提过要限制在a.begin() i 1而不是整个数组。如果写全程查找当 a[i]-d 很小、lb 总是 1 时没问题但数据一旦让 lb 超过 i就会把 L 算到 R 右边程序提前 continue导致本应可分的方案被判成无解。6.2 考场上如何避坑我在考场上的习惯是动态规划题先写个小数据暴力验证思路。比如随机生成长度不超过 8 的数组把暴力的分组枚举和 DP 结果对拍确认转移方程没写歪。这个习惯救过我很多次学习小组这道题我在草稿纸上就是这么验的。另外如果时间只剩十五分钟线段树版本比单调队列版本更值得写。因为线段树的查询逻辑一眼能看懂出错概率低单调队列虽然代码短但窗口边界想不清楚反而容易写崩。GESP 七级拿分优先不要为了炫技选风险更高的实现。7. 从学习小组延伸开备考 GESP 七级 DP 题的思路7.1 同类题目怎么迁移学习小组本质上是一个一维数组连续分段 段约束的模型。这个模型在 GESP 七级里面非常常见换一层皮就可以变成很多题目把极差不超过 d换成段内所有数乘积不超过某个上限就是一类分段可行性题把最少组数换成最大组数状态含义和转移式都要调整但窗口维护的思路一致把一维数组换成树上的路径就是树上 DP 的入门形态。所以我在备考时会把这类题归成一个专题先排序再证明连续段性质然后 dp[i] 表示前缀最优解最后用单调队列或线段树优化转移。这个套路一套一个准。7.2 我的个人体会这道题让我最受用的是没思路时先证明结构性质这个习惯。考场上很多人卡住是因为一直在想怎么分组而不是先问最优分组可能长什么样。一旦证明最优解一定是排序后的连续段问题难度立刻从指数级降到多项式级。如果你也在备考 GESP 七级我建议别只刷真题答案试着把每道题的结构性质写在题解第一行。比如学习小组的第一行就写排序后合法分组等价于把数组切成若干连续段每段满足长度 ≥ k 且首尾差 ≤ d。有这个性质在后面 DP 只是按图索骥。最后分享一个小技巧这种分段 DP 的题目写完代码后一定补测全部学生能合成一组和完全无法分组两个极端用例。前者用 d 很大的数据后者用 d0 且某些能力值人数少于 k 的数据。这两个用例能同时检验转移方程和边界条件我在实际比赛里靠这个习惯避免过不少无效提交。