结构体排序
结构体排序
引入¶
在实际开发中，我们经常需要将多个不同类型的数据组合在一起描述一个完整的对象。例如，一个学生的资料可能包括姓名、年龄、分数等信息。
如果没有结构体，我们只能定义多个变量：
string name;
int age;
double score;
这样不仅不便于管理，还容易出错。而结构体允许我们将这些相关的数据组合成一个整体，使代码更清晰、逻辑更清楚，便于维护。
定义结构体¶
结构体（struct）是用于将多个不同类型的数据组合在一起的一种用户自定义类型。
struct Student
{
string name;
int age;
double score;
};
其中 Student 是结构体的名称，它可以是任何有效的标识符（变量名）。
简单解释即自定义了一个新类型，名字叫做 Student
注意：结构体定义结束后需要有分号 ;。
结构体变量的定义¶
Student s1; // 定义一个结构体变量
Student s2 = {"Tom", 18, 92.5}; // 初始化结构体变量
也可以定义多个变量：
struct Student
{
string name;
int age;
double score;
} s3, s4;
访问结构体成员¶
使用点号 . 来访问结构体成员：
s1.name = "Alice";
s1.age = 17;
s1.score = 88.5;
cout << s1.name << " " << s1.age << " " << s1.score;
结构体数组¶
可以定义结构体数组来存储多个结构体元素：
struct Student
{
string name;
int age;
double score;
};
Student a[105]; // 存储最多 105 个学生信息
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].name >> a[i].age >> a[i].score;
}
结构体作为函数参数¶
可以将结构体作为参数传入函数：
struct Student
{
string name;
int age;
double score;
};
void print(Student s)
{
cout << s.name << " " << s.age << " " << s.score << endl;
}
int main()
{
Student x = {"Bob", 16, 85.0};
print(x);
return 0;
}
结构体是 C++ 中非常常用的基础构造类型，尤其在处理多个相关字段时非常有用。
结构体排序¶
结构体是信息学竞赛中非常常见的数据结构，结构体排序更是常考基础操作。本文将从竞赛角度讲解结构体排序的技巧、常见用法与题型示例。
预备知识：sort 函数的第三个参数¶
在 C++ 中，sort 函数可以用于排序数组，它的语法如下：
sort(起始地址, 结束地址, 比较函数);
例如我们要对一个 int 数组从大到小排序：
#include
using namespace std;
int n, a[105];
bool cmp(int x, int y)
{
return x > y; // 降序
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
}
解释：
a + 1 是起始地址，a + n + 1 是结束地址（不包含）
第三个参数是一个比较函数，返回 true 表示 x 应排在 y 前面
若省略第三个参数，则默认使用 < 比较，得到升序排序
这在结构体排序中也一样适用，只不过我们需要自定义结构体的比较方式。
引入：结构体排序的意义¶
在实际题目中，我们经常需要按照多个条件对数据进行排序。比如：
有若干名学生，每人有语文成绩和总成绩。
要求先按语文成绩升序排序，若语文成绩相同，则按总成绩降序排序。
这类问题中，单靠基本数组或双重排序是无法高效解决的。我们需要借助结构体来封装每个学生的多个字段，然后使用自定义规则排序。
结构体排序的基本语法（C++）¶
我们不能直接使用 sort(a + 1, a + n + 1); 或 sort(a, a + n); 来对结构体数组排序，因为结构体并不支持默认的比较运算。
结构体是自定义的类型，不能直接使用 < 或 > 进行比较。
struct Student
{
int chinese; // 语文成绩
int total; // 总分
};
int main()
{
Student s1 = {90, 300};
Student s2 = {85, 290};
// 错误：不能直接比较结构体
if (s1 < s2) { ... } // 编译错误
}
必须自定义一个比较函数来定义排序规则。
必须自定义一个比较函数，通过 sort 的 第三个参数 传入。
示例：按语文升序，总分降序排序¶
struct Student
{
int chinese; // 语文成绩
int total; // 总分
} a[105];
bool cmp(Student a, Student b)
{
if (a.chinese != b.chinese)
return a.chinese < b.chinese;
else
return a.total > b.total;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].chinese >> a[i].total;
sort(a + 1, a + n + 1, cmp); // 使用自定义比较函数
for (int i = 1; i <= n; i++)
cout << a[i].chinese << " " << a[i].total << endl;
return 0;
}
解释：
sort 是 C++ STL 提供的排序函数，默认只支持基本类型
结构体需要自定义比较方式，作为 sort 的第三个参数传入
总结¶
结构体排序在信息学竞赛中非常常见，是基础数据处理的关键技能。熟练掌握以下几点尤为重要：
灵活使用自定义 cmp 函数
多关键字排序的结构
注意返回值和比较方向
熟能生巧，多练习是关键！
系统自带的结构体¶
C++ STL 中提供了一个内置的结构体模板：pair
例如：
pair
pair
访问结构体的成员：
pair
a.first = 1; // 设置第一个元素
a.second = "Hello"; // 设置第二个元素
cout << a.first << " " << a.second; // 输出第一个和第二个元素
pair
优点¶
pair 提供了默认的比较方式。可以直接使用 < 和 > 进行比较
默认比较方式：先比较第一个元素，若相同再比较第二个元素。
pair
pair
if (a < b) // 比较 a 和 b
{
cout << "a < b" << endl;
}
else
{
cout << "a >= b" << endl;
}
在这个例子中，$a\geq b$。
使用 pair 进行排序
#include
using namespace std;
int n;
pair
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].first >> a[i].second; // 输入第一个和第二个元素
}
sort(a + 1, a + n + 1); // 使用默认比较方式排序
for (int i = 1; i <= n; i++)
{
cout << a[i].first << " " << a[i].second << endl; // 输出排序结果
}
}
缺点¶
pair 只能存储两个元素，如果需要存储多个元素，则需要使用结构体或 pair 的嵌套。
pair
注意 pair
例题¶
[NOIP2005 提高组] 谁拿了最多奖学金¶
题意解析
给定若干学生的考试和综合信息，判断他们能获得哪些奖学金并统计：
每位学生获得的总奖金
所有学生获得的奖金总额
奖金最多的学生（若多人奖金相同，取输入中最早出现的）
奖学金种类与条件
奖学金名称
奖金
条件
院士奖学金
$8000$
期末 $> 80$ 且 论文 $≥ 1$
五四奖学金
$4000$
期末 $> 85$ 且 班评 $> 80$
成绩优秀奖
$2000$
期末 $> 90$
西部奖学金
$1000$
期末 $> 85$ 且 西部学生
班级贡献奖
$850$
班评 $> 80$ 且 是学生干部
解题思路
定义结构体存储每位学生信息：姓名、各项成绩、是否学生干部、是否西部、论文数、奖金等。
struct Student
{
string name; // 姓名
int sum1, sum2; // 期末和评议成绩
char x, y; // 学生干部，西部学生
int num; // 论文数
int money; // 奖学金数
} a[105];
遍历每位学生，根据条件计算其可得奖金并累加总奖金。
可以定义一个 calc() 函数来计算每位学生的奖金。
void calc(Student s)
{
if (s.sum1 > 80 && s.num >= 1) s.money += 8000; // 院士奖学金
if (s.sum1 > 85 && s.sum2 > 80) s.money += 4000; // 五四奖学金
if (s.sum1 > 90) s.money += 2000; // 成绩优秀奖
if (s.sum1 > 85 && s.y == 'Y') s.money += 1000; // 西部奖学金
if (s.sum2 > 80 && s.x == 'Y') s.money += 850; // 班级贡献奖
}
在遍历过程中维护两个信息：
当前最大个体奖金及对应学生下标
所有学生奖金总额
输出：奖金最多学生姓名、奖金数、总奖金。
样例分析
输入：
4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1
处理过程：
YaoLin 得五四奖（4000）+学生干部奖（850）= 4850
ChenRuiyi 得院士奖（8000）+西部奖（1000）= 9000
LiXin 得成绩优奖（2000）+五四奖（4000）= 6000
ZhangQin 得院士奖（8000）+学生干部奖（850）= 8850
总奖金：4850 + 9000 + 6000 + 8850 = 28700
输出：
ChenRuiyi
9000
28700
注意事项与易错点
奖金条件是 $>$ 不是 $\geq $
学生可同时满足多个条件，要累加奖金
如果奖金最高有多人，取最早出现者（记录下标）
注意使用结构体封装学生信息，更清晰易维护
[NOIP2007 普及组] 奖学金¶
题目简要回顾
给定 $n$ 位学生，每人三门课（语文、数学、英语）成绩，要求：
计算总分（语文 + 数学 + 英语）
排序规则：
总分高优先
总分相同 $\to$ 语文成绩高优先
总分、语文都相同 $\to$ 学号小优先
输出前 $5$ 名学生的 学号 和 总分
数据结构选择
我们使用结构体 Student 来封装每位学生的成绩及相关信息：
struct Student
{
int id; // 学号
int chinese; // 语文
int math; // 数学
int english; // 英语
int total; // 总分
} a[305];
读取输入时，计算每个学生的总分并填入结构体数组。
求解前 $5$ 名学生时，使用 cmp 函数对结构体数组进行排序。
cmp 比较函数讲解
排序优先级：
总分 $>$ 语文 $>$ 学号
bool cmp(Student a, Student b)
{
if (a.total != b.total)
return a.total > b.total; // 总分高优先
else if (a.chinese != b.chinese)
return a.chinese > b.chinese; // 语文高优先
else
return a.id < b.id; // 学号小优先
}
说明：
若总分不同，则按总分降序排列；
若总分相同，再按语文成绩降序排列；
若仍相同，学号小的排在前面。
小结
使用结构体方便管理每位学生的多个成绩；
使用自定义 cmp 函数实现多重排序优先级；
注意 sort 的起止范围
病人排队¶
题目要求
病人按照一定规则排队看病，规则如下：
年龄 $\geq 60$ 岁的病人属于老年人，优先于非老年人看病；
老年人内部按照年龄从大到小排序；
如果老年人年龄相同，则按照登记顺序（即输入顺序）看病；
非老年人按照登记顺序看病。
解题思路
我们可以定义一个结构体 node 来存储每个病人的信息：
name：病人的姓名代号
age：病人的年龄
order：病人的登记顺序（输入的顺序，从 $0$ 开始）
接着，使用 sort 排序，并自定义排序规则。
自定义排序规则
这里要对人的年龄分类处理。
例如定义 bool cmp(node a, node b) 的函数，用于比较两个结构体元素 $a,b$ 的优先级情况。
当 $a,b$ 都是老年人，则年龄大的优先。否则按照登记顺序。
当 $a$ 是老年人，$b$ 不是，则 $a$ 优先。
当 $b$ 是老年人，$a$ 不是，则 $b$ 优先。
当 $a,b$ 都不是老年人，则按照登记顺序。
bool cmp(node a, node b)
{
if (a.age >= 60 && b.age >= 60)
{
if (a.age != b.age) return a.age > b.age; // 年龄大优先
else return a.order < b.order; // 年龄相同，登记早的优先
}
else if (a.age >= 60)
{
return true; // a 是老年人，b 不是
}
else if (b.age >= 60)
{
return false; // b 是老年人，a 不是
}
else
{
return a.order < b.order; // 都不是老年人，按登记顺序
}
}
[NOIP2009 普及组] 分数线划定¶
题目分析
给定 $n$ 个报名参加笔试的志愿者，每人有一个报名号和笔试成绩。
根据计划录取人数 $m$，我们要选出分数排名前 $m \times 1.5$ （向下取整）的人作为面试资格线，然后将分数大于等于面试线的所有人全部输出。
排序规则：
笔试成绩高的在前；
若成绩相同，报名号小的在前。
思路
定义结构体 node 存储每个志愿者的信息：
struct node
{
int id; // 报名号
int score; // 笔试成绩
} a[5005];
排序规则：
先比较分数，分数相同在比较报名号。
bool cmp(node a, node b)
{
if (a.score != b.score)
return a.score > b.score; // 成绩高的在前
return a.id < b.id; // 成绩相同则报名号小的在前
}
具体实现
首先执行结构体排序。
排序后求出 $m=m\times 1.5$ 的向下取整值，记为 m。
分数线即为 a[m].score。
进面试人数可以遍历整个结构体数组求出。
最终整体复杂度为 $O(n\log{n})$。来自于 sort 函数的排序。
最年长的人¶
小技巧：
对于固定的输入格式来说，例如本题可以看作是：
数字 + 字符 - + 数字 + 字符 - + 数字。
不一定非得用字符串处理，而是用若干个变量进行提取关键信息。
例如：
struct node
{
int year; // 年
int month; // 月
int day; // 日
} a[100005];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int y, m, d;
char ch; // 用于读取字符 '-'
cin >> y >> ch >> m >> ch >> d; // 读取格式为 "年-月-日"
a[i].year = y;
a[i].month = m;
a[i].day = d;
}
// 接下来可以对 a 数组进行排序或其他操作
}
接下来实现排序函数即可。
bool cmp(node a, node b)
{
if (a.year != b.year)
return a.year < b.year; // 年份小的在前
if (a.month != b.month)
return a.month < b.month; // 月份小的在前
return a.day < b.day; // 日期小的在前
}
最终时间复杂度为 $O(n\log{n})$，来自于 sort 函数的排序。
[ABC228C] Final Day¶
先按照前三天的成绩，我们可以从大到小排序，得到每个人的排名。
若一个人有可能进入前 $k$ 名，我们就往运气最好的情况思考。
即这个人考了 $300$ 分，其余人都是 $0$ 分，即这个人的成绩加上 $300$ 大于等于第 $k$ 名的成绩，那么这个人就是有可能的。
直接按照分值排序会打乱下标，因此使用结构体排序，结构体记录两个元素，一个是前三天分数的总和，另一个是每个人的编号，记录答案需要按照编号记录，最后按照编号从小到大去输出。
此题只有两个信息，可以用 pair 结构体来存储。
定义一个 pair
pair
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
int x, y, z;
cin >> x >> y >> z;
a[i].first = x + y + z; // 前三天分数总和
a[i].second = i; // 编号
}
接下来调用 sort(a + 1, a + n + 1, greater
[ABC229C] Cheese¶
容易发现优先使用单位美味度尽量大的奶酪，以使得总美味度最大。
因此使用结构体或者 pair 来进行排序，排序规则比较单一：
按照单位美味度从大到小排序。
排序后遍历所有奶酪求答案即可。
时间复杂度的瓶颈在于排序，复杂度为 $O(n\log{n})$。