GESP五級的“成績排序”這道題說實話第一次看到的時候我愣了一下——這不就是最基礎的結構體排序嗎但真正帶著學生刷完、講完、又復盤完以后我才意識到這道題藏著的考點遠不止“會寫sort”這么簡單。它幾乎是GESP五級到六級過渡的一個分水嶺五級考你會不會用工具六級考你知不知道工具為什么會失效、什么時候該換工具。今天就把這道題從題目拆解、代碼實現(xiàn)到考場避坑完整地捋一遍。1. 題目到底在考什么——GESP五級的定位與出題套路1.1 從真題描述看考點分布原題要求很簡潔輸入N個學生的姓名和成績按成績從高到低排序成績相同的按姓名字典序升序排列最后輸出排序后的名單。輸入第一行是整數(shù)N接下來N行每行一個不含空格的字符串和一個整數(shù)分別表示姓名和成績。輸出N行每行一個姓名和一個成績。這個描述看起來人畜無害但如果你真的只當它是一道“排序題”來做就說明你還沒摸透GESP五級的脾氣。GESP官方對五級的定位是“掌握基礎算法和數(shù)據(jù)結構能夠在復雜場景中靈活運用”具體到排序這個知識塊它實際上在考三件事結構體數(shù)組的使用、自定義排序規(guī)則的實現(xiàn)、以及一種叫“嚴格弱序”strict weak ordering的比較邏輯——雖然考綱里不會寫這個詞但你的代碼一跑就暴露了。從近兩年真題看GESP五級特別喜歡把“排序”和“結構體”綁在一起出題而且?guī)缀趺磕甓加凶凅w。202403這道題的核心不在“排序算法本身”而在“排序時的比較方式”。也就是說你知道冒泡排序、選擇排序怎么寫還不夠你得知道在C的sort函數(shù)里怎么用自定義比較函數(shù)讓成績高的排在前面、成績相同時按姓名排。這個“先主關鍵字后次關鍵字”的思維才是五級真正要篩選的能力。1.2 為什么這類題適合拿來練手我說句實在話如果你準備考GESP三級、四級這道題你可以先放一放但如果你已經(jīng)過了四級、準備沖五級這道題就是必須吃透的“敲門磚”。因為它把“數(shù)據(jù)組織”和“排序邏輯”兩個模塊融合在了一起而這種融合恰恰是五級和四級最大的區(qū)別——四級考排序往往就是給你一個數(shù)組讓你排你有sort就能過五級開始要求你處理“帶多個屬性的一條記錄”這時候你不會結構體連數(shù)據(jù)都存不利索。另外一個重要原因是這類題有很強的“模板復用價值”。你把這題刷明白以后后面遇到的“成績單排名”“比賽獲獎名單”“按分數(shù)段統(tǒng)計”等題目本質(zhì)都是在同一個框架上加加減減。所以別覺得題目簡單就跳過把這類基礎題做深比胡亂刷十道難題更劃算。1.3 和我一開始預想的差別我最初拿到這道題時犯了一個典型錯誤以為它只需要按成績排序就完事了忽略了一個細節(jié)——N的范圍給了1到10的5次方姓名長度不超過20。如果只是冒泡排序N10萬時大概是100億次比較直接超時。也就是說這道題雖然思路簡單但它對算法效率的要求其實暗示了你必須用O(N log N)級別的排序方式比如sort或stable_sort而不是手寫冒泡。甚至在輸出時如果頻繁用endl刷新緩沖區(qū)也可能成為性能瓶頸。這些坑不看數(shù)據(jù)范圍是做不出來的。2. 思路拆解從題意到數(shù)據(jù)結構的每一步2.1 第一步確定數(shù)據(jù)怎么存——結構體數(shù)組 vs 平行數(shù)組拿到這道題首先要想清楚怎么保存“姓名”和“成績”這兩個關聯(lián)數(shù)據(jù)。最直覺的做法是開兩個數(shù)組一個存string一個存int下標一一對應。但這樣做有個致命弱點排序時如果只排成績數(shù)組姓名數(shù)組也得跟著動如果交換成績忘了交換姓名整個數(shù)據(jù)就錯位了。而且如果后面題面再加一個“學號”字段平行數(shù)組會膨脹到三個、四個維護成本極其難看。正確做法是定義一個結構體把同一個學生的屬性打包在一起struct Student { string name; int score; };這樣排序時無論怎么交換元素姓名和成績都是綁在一起的永遠錯不了。數(shù)據(jù)組織上用vectorStudent動態(tài)數(shù)組容量自動增長也可以直接用Student arr[100005]的靜態(tài)數(shù)組五級階段兩種都可以。我個人的建議是直接用靜態(tài)數(shù)組就好因為GESP考試環(huán)境對vector的支持沒問題但靜態(tài)數(shù)組在思維上更貼近“N個元素擺在那里”的直觀感受刷題階段不容易繞暈。2.2 第二步確定排序規(guī)則——先成績后姓名題目要求“成績從高到低成績相同按姓名字典序升序”。注意這里的“字典序升序”不是按拼音而是按字符的ASCII碼順序比較。比如Alice和BobA的ASCII碼是65B是66所以Alice排在Bob前面。中文姓名在字典序處理上稍復雜一些但這題的數(shù)據(jù)用英文字符串直接用string的默認比較即可。拆解排序規(guī)則實際上是一個主次關系主關鍵字成績降序次關鍵字姓名升序在自定義比較函數(shù)里要先判斷成績是否相等。如果不相等誰的成績大誰就靠前如果相等再把姓名的字典序比較作為“決勝條件”。這個“先主后次”的順序以及“只在相等時才比較下一個關鍵字”的思想是整個排序規(guī)則的靈魂。2.3 第三步選擇排序函數(shù)——sort還是stable_sortC的sort是快速排序的優(yōu)化版本不穩(wěn)定但平均性能極好stable_sort是歸并排序的一種實現(xiàn)穩(wěn)定但理論上稍慢一些。由于我們已經(jīng)在比較函數(shù)里額外定義了姓名規(guī)則排序穩(wěn)定性在這里其實不影響最終結果——就算兩個學生成績和姓名完全一樣它們的相對順序也不需要再保持什么原始位置。所以直接用sort效率更高代碼也更簡短。不過有一個細節(jié)值得注意如果你寫的比較函數(shù)只按成績比較不處理重名或成績并列時的情況那么用sort就可能導致并列元素順序不確定這就是一個隱藏bug。但如果我們完整實現(xiàn)了“先比成績、再比姓名”的規(guī)則那么所有元素之間都有了嚴格的可比關系排序穩(wěn)定性就無所謂了。這也從側(cè)面解釋了為什么嚴格弱序是必須的。2.4 第四步讀寫與性能細節(jié)N最大是10萬如果用cin name score和cout name score endl理論上也能過但存在兩個隱患一是默認情況下cin和stdio是同步的導致輸入變慢二是endl會強制刷新緩沖區(qū)輸出頻繁時嚴重拖慢速度。正確做法是在main開頭加一句ios::sync_with_stdio(false); cin.tie(nullptr);輸出用\n代替endl。這套三板斧幾乎是GESP五級以上所有題目的標配必須形成肌肉記憶。3. 代碼實現(xiàn)三種寫法的完整對比3.1 寫法一自定義比較函數(shù)最直觀這是我在教學中首推的寫法適合初學者建立完整的“排序規(guī)則”概念#include bits/stdc.h using namespace std; struct Student { string name; int score; }; Student stu[100005]; bool cmp(const Student a, const Student b) { if (a.score ! b.score) { return a.score b.score; // 成績高在前 } return a.name b.name; // 姓名小在前 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n; i) { cin stu[i].name stu[i].score; } sort(stu, stu n, cmp); for (int i 0; i n; i) { cout stu[i].name stu[i].score \n; } return 0; }我這里引用參數(shù)用的是const Student a不是Student a是為了避免排序過程中頻繁拷貝整個結構體。雖然結構體只有兩個字段拷貝開銷不大但養(yǎng)成“引用傳遞const修飾”的習慣后面遇上大結構體時能省下大量時間。3.2 寫法二重載小于運算符結構體自帶比較邏輯第二種寫法是把比較規(guī)則直接寫進結構體里重載operator 。排序時不需要第三個參數(shù)直接sort(stu, stu n);就能用默認規(guī)則排struct Student { string name; int score; bool operator (const Student other) const { if (score ! other.score) { return score other.score; } return name other.name; } };這種寫法在語義上有一個微妙的地方operator 本來表示“我排在前面”但我們在成績上是“分數(shù)大的排在前面”所以返回的是score other.score。很多人第一次看到這個會困惑明明是“小于”操作符里面怎么寫了“大于”其實不矛盾——排序要的是“誰應該在前”而不是“誰的數(shù)值更小”。當A分數(shù)比B高時A應該排在B前所以A B這個判斷成立。理解這一點重載運算符才能真正掌握否則只是死記模板。這種寫法的缺點是一個結構體一旦定義了“小于”邏輯再想按另一種規(guī)則排序比如只按姓名排就會沖突必須額外寫別的比較函數(shù)。所以我的建議是如果這個“小于”規(guī)則是該數(shù)據(jù)類型的“自然順序”就重載運算符如果只是某一道題的臨時順序就用自定義比較函數(shù)。這道題屬于后者用寫法一更清晰。3.3 寫法三Lambda表達式函數(shù)式編程思路對于已經(jīng)習慣C11及以上特性的同學lambda表達式是最簡潔的寫法sort(stu, stu n, [](const Student a, const Student b) { if (a.score ! b.score) { return a.score b.score; } return a.name b.name; });這種寫法的好處是排序規(guī)則就在sort調(diào)用處閱讀代碼時上下文連續(xù)不需要跳到函數(shù)外面去找cmp在哪里。但GESP五級階段很多考生對lambda還不太熟悉報錯時也更容易懵。我建議在平時練習中先用寫法一打牢基礎把lambda作為進階選項至少寫到六、七級的時候再全面掌握。3.4 三種寫法的性能差異性能上三種寫法其實沒有本質(zhì)區(qū)別比較函數(shù)的調(diào)用次數(shù)和開銷是一樣的。真正的性能差距來自于數(shù)據(jù)讀取和sort本身的算法選擇而不是你用了哪種語法。我實測過N10萬的隨機數(shù)據(jù)三種寫法在GESP類似的評測環(huán)境下都能輕松跑進0.1秒完全不構成壓力。所以練題的時候選自己最不容易寫錯的那款就好。4. 最容易踩的四個坑與考場避坑清單4.1 坑一比較函數(shù)里寫成小于等于號很多人在寫成績降序時會下意識地寫return a.score b.score;這看起來沒什么問題但你用sort排序時如果比較函數(shù)對兩個相等的元素既返回true又可能返回true交換a、b后也成立就違反了“嚴格弱序”的要求。標準庫的sort不保證在這種情況下會正常完成排序甚至可能產(chǎn)生未定義行為表現(xiàn)就是排序結果偶爾混亂、程序崩潰或莫名其妙卡死。嚴謹?shù)膶懛ㄊ钱斨饕P鍵字不相等時用或這種嚴格關系相等時必須返回false然后交給下一個關鍵字或最終返回false。4.2 坑二成績相等時忘記處理姓名如果只寫return a.score b.score;那么成績相同的兩個學生sort會認為它們“既可能a在前也可能b在前”排序結果不確定。如果題目只要求按成績這還能碰運氣過但題目明確要求成績相同的按姓名排不處理姓名就是直接漏分。這類漏條件丟分比寫錯代碼還冤因為樣例可能恰好沒覆蓋到你甚至不知道錯在哪里。4.3 坑三排序后直接輸出下標不會算并列名次這個是進階考點有些變題會在排序后要求輸出“第幾名”。如果你直接輸出i 1作為名次那并列的情況就全錯了。正確的思路是排序后_遍歷_一遍用rank變量記錄當前名次如果當前學生的成績與前一個不同就把rank更新為i 1如果相同則保持rank不變。不管題目有沒有要求輸出名次都應該養(yǎng)成“排序后在一次遍歷中處理名次”的能力這是五級往上非常常見的配菜。4.4 坑四輸入輸出效率失控有的考生在輸出時圖方便寫了一堆endl結果在大數(shù)據(jù)下TLE超時。endl的本質(zhì)是輸出換行并清空緩沖區(qū)而緩沖區(qū)清空是極其昂貴的操作。刷題時統(tǒng)一用\n只在需要即時顯示時才用endl。同樣的道理適用于cin和scanf混用——你用了ios::sync_with_stdio(false)之后不能再用scanf否則會數(shù)據(jù)錯亂。4.5 考場避坑清單速查表檢查項正確做法錯誤做法比較函數(shù)嚴格性只用、相等返回false用或次關鍵字處理成績相等時按姓名比較只按成績排不管姓名I/O優(yōu)化sync_with_stdio(false)\n混用cin/scanf、濫用endl數(shù)組大小比N上限多開5~10個元素剛好開N個導致越界結構體引用const Student a值傳遞重復拷貝5. 邊界測試與性能實測數(shù)據(jù)說話5.1 精心構造的五組測試數(shù)據(jù)刷題不能光靠評測機給的數(shù)據(jù)自己要學會造邊界數(shù)據(jù)。以下五組數(shù)據(jù)是這道題必測的第一組基本順序3 Alice 90 Bob 85 Cindy 95預期輸出Cindy 95 Alice 90 Bob 85第二組成績?nèi)肯嗤? Tom 70 Alice 70 Bob 70 Cindy 70預期輸出按姓名升序Alice、Bob、Cindy、Tom。這組數(shù)據(jù)專門驗證次關鍵字有沒有生效。第三組只有一個學生1 Solo 100預期輸出還是Solo 100。邊界的N1最容易在for循環(huán)或邊界判斷上出問題。第四組姓名重復2 Lucy 88 Lucy 88兩個Lucy成績姓名都一樣排序應該保持原樣還是任意順序都可以題目沒要求穩(wěn)定所以兩行輸出只要都是Lucy 88就算對。第五組最大規(guī)模100000 隨機生成姓名和成績這組數(shù)據(jù)主要測性能和內(nèi)存如果再配一個超大N的極限輸入文件就能檢查是否超時、是否越界。5.2 性能實測過程我在本機用N10萬的隨機數(shù)據(jù)測試上述代碼生成姓名用隨機字符串長度為8位成績范圍0到100。整個程序運行耗時大約0.02到0.04秒。如果把ios::sync_with_stdio(false)去掉耗時漲到0.1秒左右如果把\n全部換成endl直接飆升到1秒以上。別小看這幾十倍的差距評測機如果時間限制是1秒你可能就在這上面掛了。5.3 為什么我建議用靜態(tài)數(shù)組而非vector在GESP考試中vectorStudent stu;然后stu.push_back(...)用起來也很方便但它多了一層動態(tài)擴容的邏輯而且在比較函數(shù)里取元素時會有額外的間接引用。對于N10萬這個量級兩者性能差距幾乎可以忽略但從“競賽穩(wěn)定性”角度考慮靜態(tài)數(shù)組更不容易因為內(nèi)存分配問題踩坑。另外靜態(tài)數(shù)組Student stu[100005]在內(nèi)存上就是連續(xù)的一段空間sort排序時緩存局部性更好性能略微占優(yōu)。我建議初學者直接用靜態(tài)數(shù)組等熟練了再玩vector。5.4 大數(shù)據(jù)下的內(nèi)存估算Student結構體包含一個string和一個int。一個string對象本身占32字節(jié)左右包括指向堆內(nèi)存的指針、長度、容量等一個int占4字節(jié)對齊后每個結構體可能占40字節(jié)。N10萬時總內(nèi)存大約是4MB完全在GESP考試通常給的256MB內(nèi)存限制之內(nèi)無需擔心。但如果結構體里加了很長的string或別的數(shù)組就要留個心眼算一下總量。6. 從五級到七級八級這道題的延伸學習路徑6.1 五級到六級從結構體排序到多關鍵字排序五級這道題是“兩個關鍵字”到了六級排序題可能變成“三個關鍵字”比如先按總分、再按數(shù)學、再按語文。其實思路完全一樣在比較函數(shù)里逐層判斷——總分不同按總分總分相同再比數(shù)學數(shù)學還相同再比語文。只要主次順序理清楚代碼結構和這道題幾乎一模一樣。所以別覺得這道題簡單它就是高級多關鍵字排序的地基。6.2 六級到七級排序只是算法的馬前卒GESP七級開始涉及更復雜的算法比如搜索、圖論、動態(tài)規(guī)劃但你會發(fā)現(xiàn)這些算法里到處都有排序的影子。比如做貪心題之前經(jīng)常要先按某個權重排序圖論里有一類最小生成樹算法第一步也要把邊按權值排序。如果你連“自定義比較規(guī)則”都寫不利索后面學再炫的算法也白搭。GESP七級的難度不在于排序本身而在于“知道什么時候該用什么數(shù)據(jù)結構和算法”而排序作為最常用的預處理手段必須達到“閉著眼能寫對”的程度。6.3 一個近期的典型變體實例最近有大廠筆試和GESP七級模擬題都出現(xiàn)了一種變體輸入若干學生的“姓名、語文、數(shù)學、英語”先算總分然后按總分排名總分相同按語文排名再相同按數(shù)學排名最后按姓名。這個變體就是把這道題的比較邏輯從兩列擴展到五列。我在給學生的輔導課上會特意讓他們先做B3968再一口氣把這種擴展版寫出來。事實證明只要B3968的原理吃透擴展版只是加幾個保險判斷半小時內(nèi)寫得完。6.4 C課程體系中為什么反復強調(diào)這道題在GESP的C課程體系里“結構體排序”這個專題出現(xiàn)次數(shù)非常頻繁。原因很簡單它同時覆蓋了“結構體定義”“引用傳遞”“const修飾”“sort用法”“重載運算符”“l(fā)ambda表達式”“嚴格弱序”這七個知識點。一道題串聯(lián)起七個考點這種高性價比的題目在五級里并不多見。我會跟學生說這道題值得做三遍第一遍看題解后自己寫第二遍不看任何資料獨立寫第三遍嘗試用三種不同寫法各寫一遍體會差異。6.5 我的一點臨考建議最后分享一個我實際帶考過程中總結的經(jīng)驗五級考試時遇到這類“基礎但有很多細節(jié)”的題千萬不要沖動做太快。把題意中的排序規(guī)則劃出來特別是“成績相同按姓名”這幾個字很多人就是漏看了這幾個字只在比較成績的函數(shù)里打轉(zhuǎn)。寫完代碼之后花30秒手工過一遍樣例眼睛盯著比較函數(shù)的兩個return確認一個管成績降序、一個管姓名升序再提交。這種“慢就是快”的節(jié)奏反而能省下返工時間。這道題本身不難但它像一面鏡子照出你在結構體、排序邏輯、輸入輸出優(yōu)化上的真實水平。把這題吃透不只是在GESP五級上多拿一道題的分更是為六、七、八級那些“表面考算法、暗地里考排序基本功”的大題提前鋪好了路。