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