1. 考場初見這道題在整套七級卷子里是什么位置1.1 我的第一反應2025年12月那場GESP C七級考試我做完選擇、判斷和前面幾道程序題后翻到程序設計大題第一眼看到學習小組這個題目時心里先松了一口氣——看起來不復雜。但讀完題面我在草稿紙上畫了快二十分鐘才意識到這是一道典型的序列切分型動態(tài)規(guī)劃并且它同時牽涉排序、區(qū)間合法性判斷、區(qū)間最小值維護三個環(huán)節(jié)?？己蠛驼J識的同學對答案至少有兩個人因為不同原因在這題上失分一個是上來就按從小到大貪心分組樣例過了大數(shù)據(jù)一跑就錯另一個想到了用動態(tài)規(guī)劃卻漏掉了每組人數(shù)不得少于 k 人的約束轉移方程寫得半對半錯。這篇復盤就把這道題的回憶版題意、完整推導過程和 C 題解整理出來。如果你計劃備考 2026 年 3 月或 6 月的 GESP 七級認證這道題值得當作備考樣板反復刷。1.2 它為什么能拉開差距從 GESP 七級考綱來看重點覆蓋樹與圖的遍歷、最短路、最小生成樹、基礎動態(tài)規(guī)劃、二分答案等方向。學習小組表面上是一個分組模擬題實際落點卻是動態(tài)規(guī)劃而且是七級里很容易被輕視的分段 DP 方向。它不像樹形 DP 那樣有明顯遞歸結構也不像背包那樣有固定模板很多人的第一反應是能不能貪心這恰恰是題目設計得比較巧妙的地方樣例數(shù)據(jù)會引導你往貪心想但真正的數(shù)據(jù)范圍會告訴你貪心站不住腳。整套卷子做下來我的感受是這道題給的時間壓力不小前四十分鐘如果沉浸在圖論題里到這里就容易失去耐心?？梢坏┛创┧判蚝笄谐扇舾蛇B續(xù)段的本質代碼量并不多。它考的不是背模板而是現(xiàn)場建模能力。下面我從回憶版題意說起逐步給出推導和實現(xiàn)。2. 回憶版題意分組條件與輸入輸出格式2.1 記憶中的題面說明一下GESP 官方不會在考后馬上釋放完整真題所以下面這份題面是根據(jù)同場考生的回憶和我的考場印象整理出來的復現(xiàn)版核心流程和考點保持原樣具體表述、樣例數(shù)值可能和官方卷面有差異。刷題時以這個復現(xiàn)版為準思路是一致的。題目大意如下老師要把班里的 n 名學生分成若干個學習小組。每個學生有一個能力值 a[i]。老師規(guī)定每個小組至少有 k 名學生同一小組內能力值最高和最低的學生差距不能超過 d。求最少能分成多少個小組使得所有學生都恰好被分到某一個小組中。如果無法完成分組輸出 -1。輸入格式第一行三個整數(shù) n、k、d第二行 n 個整數(shù) a[1..n]。輸出格式一個整數(shù)表示最少小組數(shù)若無法分組則輸出 -1。2.2 數(shù)據(jù)范圍與時間限制雖然官方卷面給出的數(shù)據(jù)范圍我記不太準確但按七級程序設計題的通常強度大致可以按以下范圍來約束參數(shù)取值說明n1 ~ 2×10^5學生人數(shù)規(guī)模要到 O(n log n) 以內k1 ~ n每組最少人數(shù)d0 ~ 10^9能力差距上限a[i]0 ~ 10^9能力值記得用 long long 讀這個數(shù)據(jù)范圍直接排除了 O(n^2) 的暴力分組方案。也就是說正確解法的排序部分應該是 O(n log n)分組計算部分至少要壓到 O(n log n)最好是 O(n)。2.3 考點定位我在考場上把它定位成三個步驟的疊加排序先按能力值升序排序連續(xù)段建模把任意分組轉化為把排序后的數(shù)組切成若干連續(xù)段動態(tài)規(guī)劃求最少段數(shù)每段需要滿足長度 ≥ k且首尾能力差 ≤ d。這個定位過程就是解這道題的核心下面一節(jié)詳細展開。3. 解題的第一步為什么排序之后分組只可能是連續(xù)段3.1 交換論證先排序再切分一定不虧很多同學看到分組兩個字第一反應是組合數(shù)爆炸n 個學生任意分組方案數(shù)根本枚舉不完。但題目里組內能力極差不能超過 d這個條件給了強結構。先說結論一定存在一個最優(yōu)解使得每個小組在按能力值升序排序之后都是數(shù)組里的一段連續(xù)區(qū)間。換句話說不需要考慮跨段取人的分組。為什么可以用一個非常樸素的交換論證來解釋。假設排序后的數(shù)組是 b[1] ≤ b[2] ≤ ... ≤ b[n]。任意取一個最優(yōu)分組方案把某個小組的學生下標標出來。如果這個小組中有兩個學生 b[x] 和 b[y]而且 x y同時他們之間漏掉了一個下標 zx z y而這個 b[z] 被分到了其他組那么我就可以把 b[z] 拿進這個小組再從當前小組里挑一個與它交換的成員送出去。因為數(shù)組是升序的把中間值放回當前組的極差約束時組內 max 不會變大min 不會變小所以極差只會更小而被換出去的那個學生到另一個組里也不一定破壞約束因為它的能力值正好處在兩個值的中間地帶屬于兩頭都套得上的位置。反復進行這種交換最終所有小組的成員下標都會變成連續(xù)區(qū)間。用生活類比就像排隊取餐能力值從小到大排列如果一組人里面夾著另一個組的人那這兩組的成員范圍必然交錯。既然約束只關心區(qū)間內的最大最小差距那么把夾在中間的人歸到同一組只會有利于滿足極差限制。這個結論是整個解法的地基。3.2 貪心行不行反例說明貪心為什么錯排序后切連續(xù)段這個結論一出最容易想到的就是貪心從左往右掃遇到能成一組就切一組。有經(jīng)驗的選手會立刻警惕因為切分長度還要受到至少 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] 就是合法且最優(yōu)的 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也不行實際上這個數(shù)據(jù)在 k3、d4 下真的無解所以這個反例不夠有力。我需要強調最長段貪心不是錯誤在無解上而是錯誤在少數(shù)情況下能把人分完但分的組數(shù)不一定最少。不過為了行文嚴謹我建議反問一句——就算最長段貪心碰巧能把人分完你能證明它得到的組數(shù)一定最少嗎如果不能考試時就不該拿沒證明的貪心去賭。這也是為什么正確做法必須退回到動態(tài)規(guī)劃用一個可以嚴格證明的狀態(tài)轉移把所有切分方案都覆蓋到。4. 狀態(tài)設計與轉移方程序列切分DP的完整推導4.1 dp[i] 的定義和轉移式排序之后問題變成給定升序數(shù)組 a[1..n]把它切成若干連續(xù)段每段長度 ≥ k且每段首尾差值 ≤ d求最少段數(shù)。設 dp[i] 表示把前 i 個學生即 a[1..i]全部完成分組所需的最少小組數(shù)。邊界條件是 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 必須落在合法區(qū)間內。這個合法區(qū)間的左右端點可以明確算出來。令 R i - k這是 j 的上界表示最后一段至少要留 k 個人。令 threshold a[i] - d這是最后一段第一位學生能力值的下限。由于數(shù)組升序我可以二分找到第一個大于等于 threshold 的位置 lb那么 j1 ≥ lb即 j ≥ lb - 1。同時 j 不能小于 0所以左端點 L max(0, lb - 1)。因此轉移區(qū)間就是j ∈ [ L, R ]只要 L ≤ R并且這個區(qū)間里存在一個可達的 dp 值dp[i] 就能由它更新過來。4.2 這個式子怎么高效求 min dp[j]暴力做法是每次枚舉 j復雜度 O(n^2)在 n2×10^5 下直接超時。需要優(yōu)化的點很明確左側 L 和右側 R 都隨 i 單調不減。R i - k 顯然隨 i 增大而增大threshold a[i] - d 因為數(shù)組升序也隨 i 增大而增大所以 lower_bound 得到的 lb 不會往左移動L 也不會減少。既然窗口兩端都是單調的就有兩條路可走方案數(shù)據(jù)結構復雜度特點方案一線段樹維護 dp 區(qū)間最小值O(n log n)思路直白容錯高方案二單調隊列維護窗口內最小 dpO(n)代碼短但要理解單調性我個人建議考場先寫方案一確保不丟分有時間再優(yōu)化成方案二。下面兩版代碼都給出。4.3 為什么 j 區(qū)間 必須同時滿足兩個條件這里最容易漏掉的是很多選手會記得段長條件 j ≤ i-k卻忘了還有極差條件。反過來也有選手只算極差忽略了段長。這兩個條件任何一個不滿足轉移都是非法的。我從兩個角度檢查自己如果 j 太靠左說明最后一段包括了很多學生段長當然足夠但極差可能爆掉a[i] - a[j1] d不滿足題意如果 j 太靠右說明最后一段人太少可能不足 k 個也不合法。所以合法 j 必須落在左端點 L 和右端點 R的夾縫里。這個夾縫的推導既是本題的題眼也是我考場上想了最久的地方。5. C 題解線段樹版與單調隊列版5.1 先寫一版不容易錯的線段樹維護區(qū)間最小值線段樹版本思路最直接每次算出 L 和 R 后在線段樹上查詢區(qū)間 [L, R] 的 dp 最小值再用它更新 dp[i]并把 dp[i] 插入線段樹位置 i。這樣每一步都清清楚楚適合在考場上穩(wěn)扎穩(wěn)打。#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; }這里有個細節(jié)lower_bound 的查找范圍我寫的是a.begin() 1到a.begin() i 1而不是整個數(shù)組。原因很簡單最后一段的起點 j1 不可能大于 i所以只需要在前 i 個元素里找最小可行起點。寫錯成全局查找會把 j 算到 i 右邊導致非法轉移。5.2 更進一步滑動窗口單調隊列 O(n) 寫法線段樹雖然穩(wě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和手動最優(yōu)方案一致。6. 邊界數(shù)據(jù)、易錯點與考場經(jīng)驗6.1 最容易翻車的四個地方第一k1 的邊界。k1 表示每組至少一個人這時候所有人都可以被各自分成一組但如果能力極差也滿足最好當然是全部一人一組還是合并成一組顯然合并更優(yōu)所以 dp 應該找到跨度更大的合法段。代碼里 Ri-1每次新加入的 j 是 i-1滑動窗口邏輯不變?？紙鲎钊菀自谶@里栽的是想當然認為每組至少 1 人就是無腦分成 n 組忽略最少小組數(shù)的要求。第二d0 的情況。d0 意味著同一組內所有人能力值必須完全相同。排序后要切連續(xù)段每個段內部的數(shù)值都一樣。這種情況 data 中可能存在大量相同值lower_bound 找到的 lb 是第一個等于當前值的位置不會有問題但要注意如果某個值的數(shù)量少于 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可能是負數(shù)也可能超過 int 范圍。我見過有人用 int 存差值導致負數(shù)溢出判錯。穩(wěn)妥做法是 a 數(shù)組、d、threshold 全部聲明 long long。第四lower_bound 的終點寫錯。前面提過要限制在a.begin() i 1而不是整個數(shù)組。如果寫全程查找當 a[i]-d 很小、lb 總是 1 時沒問題但數(shù)據(jù)一旦讓 lb 超過 i就會把 L 算到 R 右邊程序提前 continue導致本應可分的方案被判成無解。6.2 考場上如何避坑我在考場上的習慣是動態(tài)規(guī)劃題先寫個小數(shù)據(jù)暴力驗證思路。比如隨機生成長度不超過 8 的數(shù)組把暴力的分組枚舉和 DP 結果對拍確認轉移方程沒寫歪。這個習慣救過我很多次學習小組這道題我在草稿紙上就是這么驗的。另外如果時間只剩十五分鐘線段樹版本比單調隊列版本更值得寫。因為線段樹的查詢邏輯一眼能看懂出錯概率低單調隊列雖然代碼短但窗口邊界想不清楚反而容易寫崩。GESP 七級拿分優(yōu)先不要為了炫技選風險更高的實現(xiàn)。7. 從學習小組延伸開備考 GESP 七級 DP 題的思路7.1 同類題目怎么遷移學習小組本質上是一個一維數(shù)組連續(xù)分段 段約束的模型。這個模型在 GESP 七級里面非常常見換一層皮就可以變成很多題目把極差不超過 d換成段內所有數(shù)乘積不超過某個上限就是一類分段可行性題把最少組數(shù)換成最大組數(shù)狀態(tài)含義和轉移式都要調整但窗口維護的思路一致把一維數(shù)組換成樹上的路徑就是樹上 DP 的入門形態(tài)。所以我在備考時會把這類題歸成一個專題先排序再證明連續(xù)段性質然后 dp[i] 表示前綴最優(yōu)解最后用單調隊列或線段樹優(yōu)化轉移。這個套路一套一個準。7.2 我的個人體會這道題讓我最受用的是沒思路時先證明結構性質這個習慣?？紙錾虾芏嗳丝ㄗ∈且驗橐恢痹谙朐趺捶纸M而不是先問最優(yōu)分組可能長什么樣。一旦證明最優(yōu)解一定是排序后的連續(xù)段問題難度立刻從指數(shù)級降到多項式級。如果你也在備考 GESP 七級我建議別只刷真題答案試著把每道題的結構性質寫在題解第一行。比如學習小組的第一行就寫排序后合法分組等價于把數(shù)組切成若干連續(xù)段每段滿足長度 ≥ k 且首尾差 ≤ d。有這個性質在后面 DP 只是按圖索驥。最后分享一個小技巧這種分段 DP 的題目寫完代碼后一定補測全部學生能合成一組和完全無法分組兩個極端用例。前者用 d 很大的數(shù)據(jù)后者用 d0 且某些能力值人數(shù)少于 k 的數(shù)據(jù)。這兩個用例能同時檢驗轉移方程和邊界條件我在實際比賽里靠這個習慣避免過不少無效提交。