结构体 排序是普及组的必考核心地基多关键字排序、数据分组排序、复杂对象排序、贪心前的预处理几乎都建立在它之上。学习目标掌握结构体定义、赋值、结构体数组掌握 sort 默认排序与自定义 cmp掌握单 / 多关键字优先级排序真题高频能独立完成结构体排序类真题PART 01一、结构体定义与访问结构体struct把不同类型、但属于同一个对象的数据打包成一个整体。struct Student { int id; // 学号 int score; // 分数 string name; // 姓名 }; // ← 末尾分号必须写 Student s1; // 单个变量 s1.score 95; // 用 “对象.字段” 访问 Student a[105]; // 结构体数组刷题最常用 cin a[1].id a[1].score;✅ 记忆要点算法题几乎都用结构体数组批量存对象访问字段一律 对象.字段数组大小按范围开足。PART 02二、sort 排序函数默认排序与 cmp头文件万能头已包含区间左闭右开 [l, r)。#include algorithm sort(起始地址, 结束地址, 比较函数);不写比较函数时默认升序sort(a,an); cmp 核心口诀cmp(x,y) 返回 true表示 x 应排在 y 前面。// 降序 bool cmpInt(int x,int y){ return x y; } // 结构体多关键字先分数降序再学号升序 bool cmp(Student x, Student y) { if (x.score ! y.score) return x.score y.score; // 第一关键字 return x.id y.id; // 第二关键字 }⚠️ 严格弱序用 /不要用 /两对象相等时必须返回 false否则 sort 行为未定义。多关键字万能法按优先级从高到低本关键字不等就返回其结果相等才进入下一级。PART 03三、万能代码模板#include bits/stdc.h using namespace std; struct Node { int x, y; }; Node a[100005]; bool cmp(Node a, Node b) { if (a.x ! b.x) return a.x b.x; // 优先级1x 降序 return a.y b.y; // 优先级2y 升序 } int main() { int n; cin n; for (int i1;in;i) cin a[i].x a[i].y; sort(a1, a1n, cmp); for (int i1;in;i) cout a[i].x a[i].y \n; }PART 04四、39 题精讲分析 折叠代码按“基础数组排序 → 单关键字/贪心 → 多关键字 → 综合进阶”分 4 组。先自己写再展开代码对照。A 组 · 基础数组排序sort / 计数 / 去极值 11 题sort 模板P1177 【模板】排序把 n 个数升序输出。直接 sort 即可注意数据可能为负、范围较大用 int 足够。查看代码int n; cin n; vectorint a(n); for (int x:a) cinx; sort(a.begin(), a.end()); for (int x:a) cout x ;去重排序P1059 [NOIP 2006 普及组] 明明的随机数去重后升序输出个数与序列。排序后只在“与前一个不同”时输出个数即不同值数量。查看代码sort(a1, a1n); int m0; for (int i1;in;i) if (i1 || a[i]!a[i-1]) b[m]a[i]; cout m \n; for (int i1;im;i) cout b[i] ;计数排序P1271 【深基9.例1】选举学生会统计每个候选人得票并按编号输出。票号即候选人编号范围 n用计数数组统计再从小到大按次数输出。查看代码int n, m, x; cin n m; vectorint cnt(n1,0); for (int i0;im;i){ cinx; cnt[x]; } for (int i1;in;i) for (int j0;jcnt[i];j) cout i ;逆序对P1116 车厢重组求把车厢排成升序所需相邻交换次数。相邻交换最少次数 逆序对个数。双重循环统计 ij 且 a[i]a[j] 的对数n 很小。查看代码long long ans0; for (int i1;in;i) for (int ji1;jn;j) if (a[i] a[j]) ans;排序取值B2158 谁考了第 k 名成绩降序输出第 k 名分数成绩互不相同。降序排序后取 a[k]或 a[k-1]按下标。查看代码sort(a1, a1n, [int](int x,int y){ return xy; }); cout a[k];找最大B2125 最高分数的学生姓名输出最高分学生姓名。边读边维护最高分与对应姓名最高分唯一。查看代码string name, ansName; int mx-1, score; for (int i0;in;i){ cin name score; if (score mx) { mxscore; ansNamename; } }稳定排序B2159 成绩排序成绩从高到低同分按输入先后稳定。用结构体存“分数 原下标”cmp 中分数相等按下标升序即保证稳定。查看代码struct S{ int score, id; string name; }; bool cmp(S a,S b){ if(a.score!b.score) return a.scoreb.score; return a.idb.id; }结构体P5744 【深基7.习9】培训学员年龄 1改名为编号再按年龄降序输出。结构体存姓名、年龄、原编号处理后按年龄降序同龄按编号排序输出。查看代码struct S{ string name; int age, id; }; for (int i0;in;i){ cin a[i].name a[i].age; a[i].age; a[i].idi; a[i].nameto_string(i); } sort(a,an,[](S x,S y){ if(x.age!y.age)return x.agey.age; return x.idy.id; });去极值P5738 【深基7.例4】歌唱比赛去掉一个最高、一个最低分后求平均。对每位评委的分数排序去掉首尾后求和再除以 (m-2)。查看代码double mx0; for (int i0;in;i){ vectorint s(m); for(intx:s)cinx; sort(s.begin(),s.end()); long long sum0; for(int j1;jm-1;j) sums[j]; mxmax(mx,(double)sum/(m-2)); }多字段排序B3968 [GESP202403 五级] 成绩排序按总分降序同分语文降序再同则学号升序。典型三关键字 cmp按优先级逐级判断。查看代码bool cmp(S a,S b){ if(a.total!b.total) return a.totalb.total; if(a.chinese!b.chinese) return a.chineseb.chinese; return a.idb.id; }排序统计P2681 众数求出现次数最多的数次数相同取较小值。排序后扫描连续相同段维护最大次数次数相同取数值小者排序后先出现即小。查看代码B 组 · 单关键字与贪心结构体 一个核心属性排序 10 题贪心P1223 排队接水按接水时间升序使平均等待最小。短作业优先。第 i 人0 起的时间被后面 n-1-i 人等待贡献 t[i]*(n-1-i)。查看代码struct P{int t,id;}; bool cmp(P a,P b){ if(a.t!b.t)return a.tb.t; return a.idb.id; } sort(v.begin(),v.end(),cmp); long long total0; for(int i0;in;i){ coutv[i].id ; total(long long)v[i].t*(n-1-i); } coutfixedsetprecision(2)(double)total/n;双指针贪心P1094 [NOIP 2007 普及组] 纪念品分组每组最多 2 件、总价 ≤ W求最少组数。排序后首尾配对能凑就两件一起否则最贵单独。查看代码sort(a,an); int i0,jn-1,ans0; while(ij){ if(ij){ans;break;} if(a[i]a[j]W)i; j--;ans; }排序贪心P1478 陶陶摘苹果升级版够得到的苹果按体力升序摘求最多个数。可达高度 ab先筛高度再按消耗体力升序贪心。查看代码int reachab; vectorint v; for(int i0;in;i){ int x,c;cinxc; if(xreach)v.push_back(c); } sort(v.begin(),v.end()); int ans0; for(int x:v)if(sx){s-x;ans;}else break;两端贪心P4995 跳跳在最高/最低石头间交替跳最大化高度差平方和。从地面 0 起先跳最高、再跳剩余最低两端交替累加落差平方long long。查看代码sort(a.begin(),a.end()); int l0,rn-1; long long now0,ans0; while(lr){ ans(a[r]-now)*(a[r]-now);nowa[r];r--; if(lr)break; ans(now-a[l])*(now-a[l]);nowa[l];l; }降序贪心P2676 [USACO07DEC] Bookshelf B牛身高降序累加到不低于书架高度。降序排序后依次累加直到总和 ≥ B。查看代码sort(a,an,[](int x,int y){return xy;}); long long sum0; for(int i0;in;i){suma[i];if(sumB){couti1;break;}}排序贪心P2695 骑士的工作龙头与骑士能力都升序用最小够用的骑士砍头。两个数组都排序双指针能力够砍当前头就计数否则换更强骑士。查看代码sort(head,headn); sort(knight,knightm); int i0,j0,cnt0; long long cost0; while(in jm){ if(knight[j]head[i]){costknight[j];cnt;i;j;} else j; } if(cntn)coutcost;else coutyou died!;高度排序P5143 攀爬者按海拔升序爬山求总路程相邻高度差之和。按高度升序排序累加相邻两点高度差。查看代码sort(a,an); double ans0; for(int i1;in;i) ansa[i]-a[i-1];中位数P1862 输油管道问题主管道东西走向选 y 使纵向支线总长最小。绝对值距离之和在中位数处最小。对所有 y 排序取中位累加 |y-中位|。查看代码sort(y,yn); int midy[n/2]; long long ans0; for(int i0;in;i) ansabs(y[i]-mid);价格贪心P1208 [USACO1.3] 混合牛奶 Mixing Milk按单价升序购买凑够需求量使花费最小。结构体存单价、数量按单价升序逐个购买直到满足需求。查看代码struct M{int price, amount;}; sort(milk,milkn,[](M a,M b){return a.priceb.price;}); long long cost0; int needtotal; for(int i0;in need0;i){ int buymin(need,milk[i].amount); cost(long long)buy*milk[i].price; need-buy; }区间贪心P2859 [USACO06FEB] Stall Reservations S求最少畜栏数并给出每头牛的栏号。按开始时间升序用小根堆维护各栏当前结束时间最早栏能复用结束当前开始就复用并更新否则新开栏记录分配的栏号。查看代码struct Cow{int l,r,id;}; sort(a,an,[](Cow x,Cow y){return x.ly.l;}); priority_queuepairint,int, vectorpairint,int, greater pq; for(int i0;in;i){ if(!pq.empty() pq.top().firsta[i].l){ ans[a[i].id]pq.top().second;pq.pop(); }else ans[a[i].id]stalls; pq.push({a[i].r,ans[a[i].id]}); }C 组 · 多关键字排序优先级逐级兜底 13 题三关键字P1093 [NOIP 2007 普及组] 奖学金总分降序、语文降序、学号升序。结构体存三科与总分三关键字 cmp。查看代码bool cmp(S a,S b){ if(a.total!b.total)return a.totalb.total; if(a.chi!b.chi)return a.chib.chi; return a.idb.id; }分数线排序P1068 [NOIP 2009 普及组] 分数线划定按 plan×1.5 取面试名额再按笔试降序、编号升序。先按笔试降序排取第 ⌊m×1.5⌋ 名成绩为线所有 ≥ 线者进面同分都进输出时保持降序、同编号升序。查看代码sort(a,an,[](S x,S y){ if(x.score!y.score)return x.scorey.score; return x.idy.id; }); int linea[(int)(m*1.5)-1].score; for(int i0;in;i) if(a[i].scoreline) couta[i].id a[i].score\n;日期多关键字P1104 生日按年、月、日升序同年同月同日先输入的在前。结构体存年月日与原序cmp 逐级升序全等按原序。查看代码bool cmp(S a,S b){ if(a.year!b.year)return a.yearb.year; if(a.month!b.month)return a.monthb.month; if(a.day!b.day)return a.dayb.day; return a.idb.id; }分组排序B2160 病人排队≥60 岁按年龄降序同龄按登记序其余按登记序。分成“老人”和“普通”两组老人按年龄降序、登记序排前面普通组保登记序接在后面。查看代码struct S{string id;int age,ord;}; vectorS old, normal; for(int i0;in;i){ if(a[i].age60)old.push_back(a[i]); else normal.push_back(a[i]); } sort(old.begin(),old.end(),[](S x,S y){ if(x.age!y.age)return x.agey.age; return x.ordy.ord; });取第一P5740 【深基7.例9】最厉害的学生总分降序、学号升序输出第一名三科。算总分后排序或直接维护“最优学生”输出其信息。查看代码int bestId1; for(int i1;in;i){ cina[i].c1a[i].c2a[i].c3; a[i].totala[i].c1a[i].c2a[i].c3; if(a[i].totala[bestId].total)bestIdi; }两两判断P5741 【深基7.例10】旗鼓相当的对手 - 加强版两学生每科分差绝对值都 ≤5 且总分不等即互为对手。双重循环枚举两人三科分差全 ≤5 且 total 不等则互相输出名字。查看代码for(int i1;in;i) for(int ji1;jn;j){ if(abs(a[i].c-a[j].c)5abs(a[i].m-a[j].m)5 abs(a[i].e-a[j].e)5a[i].total!a[j].total) couta[i].name a[j].name\n; }条件评级P5742 【深基7.例11】评等级综合分德育×0.7智育×0.3满足条件评优秀。按题意计算综合分可用整数放大避免浮点误差逐条判断输出。查看代码for(int i0;in;i){ int id,c1,c2;cinidc1c2; int score7*c13*c2; // 放大10倍800 即综合≥80 if(c1c2140 score800) coutExcellent\n; else coutNot excellent\n; }多规则累加P1051 [NOIP 2005 提高组] 谁拿了最多奖学金按 5 条规则累加奖学金求最大与总和。奖金可叠加期末80且论文≥1加8000期末85且评议80加4000期末90加2000西部且期末85加1000干部且评议80加850。查看代码if(s.final_80s.paper1)money8000; if(s.final_85s.cls_80)money4000; if(s.final_90)money2000; if(s.westYs.final_85)money1000; if(s.leadYs.cls_80)money850;归并优化P1309 [NOIP 2011 普及组] 瑞士轮每轮相邻对战胜/负组各自有序归并合并。每轮整体 sort 超时。赢家、输家内部仍有序用 merge 归并成新序列 O(N)。查看代码while(R--){ vectorP win,lose; for(int i0;i2*N;i2){ if(p[i].wp[i1].w){p[i].score;win.push_back(p[i]);lose.push_back(p[i1]);} else{p[i1].score;win.push_back(p[i1]);lose.push_back(p[i]);} } merge(win.begin(),win.end(),lose.begin(),lose.end(),p.begin(),cmp); }计数不重排P7910 [CSP-J 2021] 插入排序稳定排序后问 x 的名次O(n) 数前面元素不真排序。排在 x 前的 值更小的 值相等但下标更小的。每次查询 O(n) 计数。查看代码int rank0; for(int i1;in;i){ if(a[i]a[x])rank; else if(a[i]a[x]ix)rank; }频次差判素P1125 [NOIP 2008 提高组] 笨小猴字母最大/最小出现次数之差判素数。统计 26 字母频次只看出现过的dmax-mind 为素数则 Lucky Word。查看代码int mx0,mn1000; for(int x:cnt)if(x){mxmax(mx,x);mnmin(mn,x);} int dmx-mn; bool okd2; for(int i2;i*id;i)if(d%i0)okfalse;多组排序P1056 [NOIP 2008 普及组] 排座椅分别对行、列通道排序取前 k 后升序输出。统计每对相邻行/列被多少对同学隔开各自降序取前 k再把选中编号升序输出。查看代码// row[i]第 i、i1 行间被隔开的对数col 同理 sort(pickRow.begin(),pickRow.end(),greaterint()); sort(pickCol.begin(),pickCol.end(),greaterint()); vectorint R(pickRow.begin(),pickRow.begin()k); vectorint C(pickCol.begin(),pickCol.begin()l); sort(R.begin(),R.end()); sort(C.begin(),C.end());中位数P1889 [CEOI 1998] 士兵站队x、y 分别移动到连续整列最小化总步数。y 方向取中位数x 先升序排序令 b[i]x[i]-i 化为“对齐同一点”再取 b 的中位数。两方向相加。查看代码sort(x,xn); sort(y,yn); for(int i0;in;i) b[i]x[i]-i; sort(b,bn); int myy[n/2], mxb[n/2], ans0; for(int i0;in;i){ansabs(y[i]-my);ansabs(b[i]-mx);}D 组 · 综合与进阶排序为预处理主考其他算法 5 题字符串贪心P1200 [USACO1.1] 你的飞碟在这儿把彗星名/小组名各字母乘积 mod 47相等则 GO。字母 A1…Z26分别累乘取模 47比较两结果。查看代码auto code[](string s){ int p1; for(char c:s)pp*(c-A1)%47; return p; }; cout(code(comet)code(group)?GO:STAY);拓扑DPP1113 [USACO02FEB] 杂务杂务有前置依赖求完成全部的最短时间。每项最早完成时间 自身耗时 max(各前置的完成时间)。按输入顺序已是拓扑序递推最后取所有完成时间最大值。查看代码int ans0; for(int i1;in;i){ int id,t,pre,earliest0; cinidtpre; while(pre){earliestmax(earliest,f[pre]);cinpre;} f[id]earliestt; ansmax(ans,f[id]); }日期枚举P2010 [NOIP 2016 普及组] 回文日期由年份逆序构造 8 位回文日期并校验合法。对每个 4 位年份 y把其数字逆序作后 4 位得 yyyymmdd校验月日合法含闰年落在区间内则计数。查看代码auto rev4[](int y){return y%10*1000y/10%10*100y/100%10*10y/1000;}; int mdrev4(y),mmd/100,dmd%100; if(m1||m12||d1||ddayLimit(y,m))continue;字符串cmpP1012 [NOIP 1998 提高组] 拼数把若干数拼成最大的数。以字符串存储cmp 按拼接结果比较return ab ba; 排序后依次拼接。查看代码vectorstring s(n); sort(s.begin(),s.end(),[](string a,string b){return abba;}); for(string x:s)coutx;快速选择P1923 【深基9.例4】求第 k 小的数n 很大整体排序可能偏慢用快速选择 O(n)。可用 nth_element(a,ak,an) 直接把第 k 小放到第 k 位平均 O(n)手写则用快排划分、只递归含 k 的一侧。查看代码// C 最简 nth_element(a,ak,an); couta[k];PART 05五、总结与自主练习结构体 排序的核心套路只有三步先定义结构体把每个对象的多个属性打包再写 cmp 比较函数按优先级从高到低逐级判断、相等才进入下一级并补上兜底返回最后调用 sort传入起始地址和 cmp 即可完成排序。只要严格遵循“多关键字逐级判断 严格弱序相等返回 false”任何排序题都能稳定拿下。下面 5 道题从 A/B/C 组中精选覆盖基础、贪心与多关键字三大考点建议先独立完成再展开折叠代码对照重点检查自己的 cmp 是否写全、升降序是否与题意一致P1177 排序A 组sort 模板题练手基础排序与输入输出注意数据可能为负。P1059 明明的随机数A 组排序 去重练习“只在与前一个不同时输出”的经典写法。P1223 排队接水B 组单关键字贪心体会“短作业优先”如何让平均等待最小。P1094 纪念品分组B 组排序 双指针贪心练习首尾配对的最优策略。P1093 奖学金C 组三关键字排序总分降序、语文降序、学号升序直接套用万能 cmp 模板。六、易错点与自查清单结构体 / cmp 易错结构体定义末尾漏分号cmp 用 /相等返回 true破坏严格弱序多关键字顺序写反必须先高后低漏写完全相等时的兜底返回sort / 范围易错区间搞错排 1~n 写 sort(a1,a1n)数组开太小 RE该用 long long 用了 int该稳定排序没保序多轮整体重 sort 超时P1309 归并上考场前自查清单✅ 字段类型选对了吗用数组还是结构体数组✅ 各关键字及升降序写全了吗cmp 对相等返回 false 吗✅ sort 起止地址对吗数据从 0 还是 1 开始✅ 看过数据范围吗数组够大吗要不要 long long / 字符串存大数✅ 有没有多轮重排要归并 / 计数 / 快选吗✅ 这题主考点真是排序吗还是贪心 / 二分 / 分治 / 模拟 / 拓扑