体系 2 · 排序与结构体 讲义

结构体 + 排序是普及组的必考核心地基：多关键字排序、数据分组排序、复杂对象排序、贪心前的预处理，几乎都建立在它之上。

学习目标

• 掌握结构体定义、赋值、结构体数组
• 掌握 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,a+n);

💡 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; // 优先级1：x 降序 return a.y < b.y; // 优先级2：y 升序 } int main() { int n; cin >> n; for (int i=1;i<=n;i++) cin >> a[i].x >> a[i].y; sort(a+1, a+1+n, cmp); for (int i=1;i<=n;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; vector<int> a(n); for (int &x:a) cin>>x; sort(a.begin(), a.end()); for (int x:a) cout << x << " ";

去重排序P1059 [NOIP 2006 普及组] 明明的随机数

去重后升序，输出个数与序列。

排序后只在“与前一个不同”时输出；个数即不同值数量。

查看代码

sort(a+1, a+1+n); int m=0; for (int i=1;i<=n;i++) if (i==1 || a[i]!=a[i-1]) b[++m]=a[i]; cout << m << '\n'; for (int i=1;i<=m;i++) cout << b[i] << " ";

计数排序P1271 【深基9.例1】选举学生会

统计每个候选人得票并按编号输出。

票号即候选人编号（范围 n），用计数数组统计，再从小到大按次数输出。

查看代码

int n, m, x; cin >> n >> m; vector<int> cnt(n+1,0); for (int i=0;i<m;i++){ cin>>x; cnt[x]++; } for (int i=1;i<=n;i++) for (int j=0;j<cnt[i];j++) cout << i << " ";

逆序对P1116 车厢重组

求把车厢排成升序所需相邻交换次数。

相邻交换最少次数 =逆序对个数。双重循环统计 i<j 且 a[i]>a[j] 的对数（n 很小）。

查看代码

long long ans=0; for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (a[i] > a[j]) ans++;

排序取值B2158 谁考了第 k 名

成绩降序，输出第 k 名分数（成绩互不相同）。

降序排序后取 a[k]（或 a[k-1]，按下标）。

查看代码

sort(a+1, a+1+n, [int](int x,int y){ return x>y; }); cout << a[k];

找最大B2125 最高分数的学生姓名

输出最高分学生姓名。

边读边维护最高分与对应姓名；最高分唯一。

查看代码

string name, ansName; int mx=-1, score; for (int i=0;i<n;i++){ cin >> name >> score; if (score > mx) { mx=score; ansName=name; } }

稳定排序B2159 成绩排序

成绩从高到低，同分按输入先后（稳定）。

用结构体存“分数 + 原下标”，cmp 中分数相等按下标升序，即保证稳定。

查看代码

struct S{ int score, id; string name; }; bool cmp(S a,S b){ if(a.score!=b.score) return a.score>b.score; return a.id<b.id; }

结构体P5744 【深基7.习9】培训

学员年龄 +1，改名为编号，再按年龄降序输出。

结构体存姓名、年龄、原编号；处理后按年龄降序（同龄按编号）排序输出。

查看代码

struct S{ string name; int age, id; }; for (int i=0;i<n;i++){ cin >> a[i].name >> a[i].age; a[i].age++; a[i].id=i; a[i].name=to_string(i); } sort(a,a+n,[](S x,S y){ if(x.age!=y.age)return x.age>y.age; return x.id<y.id; });

去极值P5738 【深基7.例4】歌唱比赛

去掉一个最高、一个最低分后求平均。

对每位评委的分数排序，去掉首尾后求和，再除以 (m-2)。

查看代码

double mx=0; for (int i=0;i<n;i++){ vector<int> s(m); for(int&x:s)cin>>x; sort(s.begin(),s.end()); long long sum=0; for(int j=1;j<m-1;j++) sum+=s[j]; mx=max(mx,(double)sum/(m-2)); }

多字段排序B3968 [GESP202403 五级] 成绩排序

按总分降序，同分语文降序，再同则学号升序。

典型三关键字 cmp，按优先级逐级判断。

查看代码

bool cmp(S a,S b){ if(a.total!=b.total) return a.total>b.total; if(a.chinese!=b.chinese) return a.chinese>b.chinese; return a.id<b.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.t<b.t; return a.id<b.id; } sort(v.begin(),v.end(),cmp); long long total=0; for(int i=0;i<n;i++){ cout<<v[i].id<<" "; total+=(long long)v[i].t*(n-1-i); } cout<<fixed<<setprecision(2)<<(double)total/n;

双指针贪心P1094 [NOIP 2007 普及组] 纪念品分组

每组最多 2 件、总价 ≤ W，求最少组数。

排序后首尾配对：能凑就两件一起，否则最贵单独。

查看代码

sort(a,a+n); int i=0,j=n-1,ans=0; while(i<=j){ if(i==j){ans++;break;} if(a[i]+a[j]<=W)i++; j--;ans++; }

排序贪心P1478 陶陶摘苹果（升级版）

够得到的苹果按体力升序摘，求最多个数。

可达高度 a+b，先筛高度，再按消耗体力升序贪心。

查看代码

int reach=a+b; vector<int> v; for(int i=0;i<n;i++){ int x,c;cin>>x>>c; if(x<=reach)v.push_back(c); } sort(v.begin(),v.end()); int ans=0; for(int x:v)if(s>=x){s-=x;ans++;}else break;

两端贪心P4995 跳跳！

在最高/最低石头间交替跳，最大化高度差平方和。

从地面 0 起，先跳最高、再跳剩余最低，两端交替，累加落差平方（long long）。

查看代码

sort(a.begin(),a.end()); int l=0,r=n-1; long long now=0,ans=0; while(l<=r){ ans+=(a[r]-now)*(a[r]-now);now=a[r];r--; if(l>r)break; ans+=(now-a[l])*(now-a[l]);now=a[l];l++; }

降序贪心P2676 [USACO07DEC] Bookshelf B

牛身高降序，累加到不低于书架高度。

降序排序后依次累加，直到总和 ≥ B。

查看代码

sort(a,a+n,[](int x,int y){return x>y;}); long long sum=0; for(int i=0;i<n;i++){sum+=a[i];if(sum>=B){cout<<i+1;break;}}

排序贪心P2695 骑士的工作

龙头与骑士能力都升序，用最小够用的骑士砍头。

两个数组都排序，双指针：能力够砍当前头就计数，否则换更强骑士。

查看代码

sort(head,head+n); sort(knight,knight+m); int i=0,j=0,cnt=0; long long cost=0; while(i<n && j<m){ if(knight[j]>=head[i]){cost+=knight[j];cnt++;i++;j++;} else j++; } if(cnt==n)cout<<cost;else cout<<"you died!";

高度排序P5143 攀爬者

按海拔升序爬山，求总路程（相邻高度差之和）。

按高度升序排序，累加相邻两点高度差。

查看代码

sort(a,a+n); double ans=0; for(int i=1;i<n;i++) ans+=a[i]-a[i-1];

中位数P1862 输油管道问题

主管道东西走向，选 y 使纵向支线总长最小。

绝对值距离之和在中位数处最小。对所有 y 排序取中位，累加 |y-中位|。

查看代码

sort(y,y+n); int mid=y[n/2]; long long ans=0; for(int i=0;i<n;i++) ans+=abs(y[i]-mid);

价格贪心P1208 [USACO1.3] 混合牛奶 Mixing Milk

按单价升序购买，凑够需求量使花费最小。

结构体存单价、数量，按单价升序，逐个购买直到满足需求。

查看代码

struct M{int price, amount;}; sort(milk,milk+n,[](M a,M b){return a.price<b.price;}); long long cost=0; int need=total; for(int i=0;i<n && need>0;i++){ int buy=min(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,a+n,[](Cow x,Cow y){return x.l<y.l;}); priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; for(int i=0;i<n;i++){ if(!pq.empty() && pq.top().first<a[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.total>b.total; if(a.chi!=b.chi)return a.chi>b.chi; return a.id<b.id; }

分数线+排序P1068 [NOIP 2009 普及组] 分数线划定

按 plan×1.5 取面试名额，再按笔试降序、编号升序。

先按笔试降序排，取第 ⌊m×1.5⌋ 名成绩为线，所有 ≥ 线者进面（同分都进）；输出时保持降序、同编号升序。

查看代码

sort(a,a+n,[](S x,S y){ if(x.score!=y.score)return x.score>y.score; return x.id<y.id; }); int line=a[(int)(m*1.5)-1].score; for(int i=0;i<n;i++) if(a[i].score>=line) cout<<a[i].id<<" "<<a[i].score<<'\n';

日期多关键字P1104 生日

按年、月、日升序，同年同月同日先输入的在前。

结构体存年月日与原序，cmp 逐级升序，全等按原序。

查看代码

bool cmp(S a,S b){ if(a.year!=b.year)return a.year<b.year; if(a.month!=b.month)return a.month<b.month; if(a.day!=b.day)return a.day<b.day; return a.id<b.id; }

分组排序B2160 病人排队

≥60 岁按年龄降序（同龄按登记序），其余按登记序。

分成“老人”和“普通”两组：老人按年龄降序、登记序排前面；普通组保登记序，接在后面。

查看代码

struct S{string id;int age,ord;}; vector<S> old, normal; for(int i=0;i<n;i++){ if(a[i].age>=60)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.age>y.age; return x.ord<y.ord; });

取第一P5740 【深基7.例9】最厉害的学生

总分降序、学号升序，输出第一名三科。

算总分后排序，或直接维护“最优学生”，输出其信息。

查看代码

int bestId=1; for(int i=1;i<=n;i++){ cin>>a[i].c1>>a[i].c2>>a[i].c3; a[i].total=a[i].c1+a[i].c2+a[i].c3; if(a[i].total>a[bestId].total)bestId=i; }

两两判断P5741 【深基7.例10】旗鼓相当的对手 - 加强版

两学生每科分差绝对值都 ≤5 且总分不等即互为对手。

双重循环枚举两人，三科分差全 ≤5 且 total 不等则互相输出名字。

查看代码

for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ if(abs(a[i].c-a[j].c)<=5&&abs(a[i].m-a[j].m)<=5 &&abs(a[i].e-a[j].e)<=5&&a[i].total!=a[j].total) cout<<a[i].name<<" "<<a[j].name<<'\n'; }

条件评级P5742 【深基7.例11】评等级

综合分=德育×0.7+智育×0.3；满足条件评优秀。

按题意计算综合分（可用整数放大避免浮点误差），逐条判断输出。

查看代码

for(int i=0;i<n;i++){ int id,c1,c2;cin>>id>>c1>>c2; int score=7*c1+3*c2; // 放大10倍，>=800 即综合≥80 if(c1+c2>140 && score>=800) cout<<"Excellent\n"; else cout<<"Not excellent\n"; }

多规则累加P1051 [NOIP 2005 提高组] 谁拿了最多奖学金

按 5 条规则累加奖学金，求最大与总和。

奖金可叠加：期末>80且论文≥1加8000；期末>85且评议>80加4000；期末>90加2000；西部且期末>85加1000；干部且评议>80加850。

查看代码

if(s.final_>80&&s.paper>=1)money+=8000; if(s.final_>85&&s.cls_>80)money+=4000; if(s.final_>90)money+=2000; if(s.west=="Y"&&s.final_>85)money+=1000; if(s.lead=="Y"&&s.cls_>80)money+=850;

归并优化P1309 [NOIP 2011 普及组] 瑞士轮

每轮相邻对战，胜/负组各自有序，归并合并。

每轮整体 sort 超时。赢家、输家内部仍有序，用 merge 归并成新序列 O(N)。

查看代码

while(R--){ vector<P> win,lose; for(int i=0;i<2*N;i+=2){ if(p[i].w>p[i+1].w){p[i].score++;win.push_back(p[i]);lose.push_back(p[i+1]);} else{p[i+1].score++;win.push_back(p[i+1]);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 rank=0; for(int i=1;i<=n;i++){ if(a[i]<a[x])rank++; else if(a[i]==a[x]&&i<=x)rank++; }

频次差判素P1125 [NOIP 2008 提高组] 笨小猴

字母最大/最小出现次数之差判素数。

统计 26 字母频次（只看出现过的），d=max-min；d 为素数则 Lucky Word。

查看代码

int mx=0,mn=1000; for(int x:cnt)if(x){mx=max(mx,x);mn=min(mn,x);} int d=mx-mn; bool ok=d>=2; for(int i=2;i*i<=d;i++)if(d%i==0)ok=false;

多组排序P1056 [NOIP 2008 普及组] 排座椅

分别对行、列通道排序取前 k 后升序输出。

统计每对相邻行/列被多少对同学隔开，各自降序取前 k，再把选中编号升序输出。

查看代码

// row[i]：第 i、i+1 行间被隔开的对数；col 同理 sort(pickRow.begin(),pickRow.end(),greater<int>()); sort(pickCol.begin(),pickCol.end(),greater<int>()); vector<int> R(pickRow.begin(),pickRow.begin()+k); vector<int> 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,x+n); sort(y,y+n); for(int i=0;i<n;i++) b[i]=x[i]-i; sort(b,b+n); int my=y[n/2], mx=b[n/2], ans=0; for(int i=0;i<n;i++){ans+=abs(y[i]-my);ans+=abs(b[i]-mx);}

D 组 · 综合与进阶

排序为预处理，主考其他算法 5 题

字符串贪心P1200 [USACO1.1] 你的飞碟在这儿

把彗星名/小组名各字母乘积 mod 47，相等则 GO。

字母 A=1…Z=26，分别累乘取模 47，比较两结果。

查看代码

auto code=[](string s){ int p=1; for(char c:s)p=p*(c-'A'+1)%47; return p; }; cout<<(code(comet)==code(group)?"GO":"STAY");

拓扑DPP1113 [USACO02FEB] 杂务

杂务有前置依赖，求完成全部的最短时间。

每项最早完成时间 = 自身耗时 + max(各前置的完成时间)。按输入顺序（已是拓扑序）递推，最后取所有完成时间最大值。

查看代码

int ans=0; for(int i=1;i<=n;i++){ int id,t,pre,earliest=0; cin>>id>>t>>pre; while(pre){earliest=max(earliest,f[pre]);cin>>pre;} f[id]=earliest+t; ans=max(ans,f[id]); }

日期枚举P2010 [NOIP 2016 普及组] 回文日期

由年份逆序构造 8 位回文日期并校验合法。

对每个 4 位年份 y，把其数字逆序作后 4 位得 yyyymmdd；校验月日合法（含闰年），落在区间内则计数。

查看代码

auto rev4=[](int y){return y%10*1000+y/10%10*100+y/100%10*10+y/1000;}; int md=rev4(y),m=md/100,d=md%100; if(m<1||m>12||d<1||d>dayLimit(y,m))continue;

字符串cmpP1012 [NOIP 1998 提高组] 拼数

把若干数拼成最大的数。

以字符串存储，cmp 按拼接结果比较：return a+b > b+a; 排序后依次拼接。

查看代码

vector<string> s(n); sort(s.begin(),s.end(),[](string a,string b){return a+b>b+a;}); for(string& x:s)cout<<x;

快速选择P1923 【深基9.例4】求第 k 小的数

n 很大，整体排序可能偏慢，用快速选择 O(n)。

可用 nth_element(a,a+k,a+n) 直接把第 k 小放到第 k 位（平均 O(n)）；手写则用快排划分、只递归含 k 的一侧。

查看代码

// C++ 最简 nth_element(a,a+k,a+n); cout<<a[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(a+1,a+1+n)；
• 数组开太小 RE；该用 long long 用了 int；
• 该稳定排序没保序；
• 多轮整体重 sort 超时（P1309 归并）；

上考场前自查清单

• ✅ 字段类型选对了吗？用数组还是结构体数组？
• ✅ 各关键字及升降序写全了吗？cmp 对相等返回 false 吗？
• ✅ sort 起止地址对吗？数据从 0 还是 1 开始？
• ✅ 看过数据范围吗？数组够大吗？要不要 long long / 字符串存大数？
• ✅ 有没有多轮重排？要归并 / 计数 / 快选吗？
• ✅ 这题主考点真是排序吗？还是贪心 / 二分 / 分治 / 模拟 / 拓扑？