第七章 结构体¶
基础数学知识¶
- 复合条件：区分“同时满足”和“满足任意一个”，对应程序中的
&&与||（1399、1839）。
1147：最高分数的学生姓名¶
提示 1：找方向
只找最高分对应的姓名，需要把所有人都存下来吗？
提示 2：推导与实现
像打擂台一样，读到更高分时，把分数和姓名一起更新。
知识补充
本题先保留边读边比较的写法，后面再用结构体把一组信息放在一起。
只在分数更高时替换，因此遇到相同最高分会保留先读到的人。
常见错误
分数更新了，姓名却没更新，会把两个人的信息混在一起。
最高分初值要小于合法成绩，不能让零分漏掉。
自测
输入：3 80 Li 95 Wang 90 Zhang → 预期输出：Wang
输入：1 0 Lin → 预期输出：Lin
参考代码
1399：甲流病人初筛¶
提示 1：找方向
体温达到要求但不咳嗽，要不要输出？
拿草稿纸列一下两个条件的组合。
提示 2：推导与实现
两个条件要同时满足，用&&连接。
每找到一名符合条件的人，就输出姓名并计数。
知识补充
node把姓名、体温和咳嗽标记组成一条病人记录。
例如x.temp表示这名病人的体温，结构体定义末尾的分号不能漏。
常见错误
体温恰好为37.5也符合体温条件，不要写成>。
姓名按输入顺序输出，最后还要输出人数。
参考代码
#include <bits/stdc++.h>
using namespace std;
struct node {
string name;
double temp;
int cough;
};
int main() {
int n, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++) {
node x;
cin >> x.name >> x.temp >> x.cough;
if (x.temp >= 37.5 && x.cough == 1) {
cout << x.name << '\n';
cnt++;
}
}
cout << cnt;
return 0;
}
1176：谁考了第 k 名¶
提示 1：找方向
第1名应该在成绩从高到低排列后的哪个位置？
再想想，数组下标从0开始，会差多少？
提示 2：推导与实现
降序排列后，第k名的下标是k - 1。
如果改用升序，下标又该怎样算？
知识补充
cmp(x, y)返回true，表示希望x排在y前面。
sort(a, a + n, cmp)排序的范围是下标0到n - 1，不包含a + n。
拓展写法用pair把成绩放在first、学号放在second，默认先比较first，相同再比较second。
优先队列默认让最大的元素在队首，弹出前k - 1个后，队首就是第k个。
常见错误
学号和成绩是一组信息，交换时必须一起移动。
成绩有小数，要用double保存。
升序取n - k，降序取k - 1，别混着用。
自测
输入：
预期输出：90788004 68.4
输入：1 1 90788001 60.5 → 预期输出：90788001 60.5
自己试试：把第一组的k分别改成1和5，先写出预期结果，再运行。
方法一：结构体排序
按成绩降序排列。
#include <bits/stdc++.h>
using namespace std;
struct node {
int id;
double score;
} a[110];
bool cmp(node x, node y) {
return x.score > y.score;
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i].id >> a[i].score;
sort(a, a + n, cmp);
printf("%d %g", a[k - 1].id, a[k - 1].score);
return 0;
}
方法二：双数组冒泡排序
按成绩升序排列，交换成绩时同步交换学号。
#include <bits/stdc++.h>
using namespace std;
int a[110];
double b[110];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
if (b[j] < b[j - 1]) {
swap(b[j], b[j - 1]);
swap(a[j], a[j - 1]);
}
}
}
cout << a[n - k] << ' ' << b[n - k];
return 0;
}
方法三：pair升序排序（拓展）
升序排列后，取下标n - k。
方法四：pair降序排序（拓展）
用greater改为降序，取下标k - 1。
方法五：优先队列（拓展）
每次弹出当前最高成绩，重复k - 1次。
1178：成绩排序¶
提示 1：找方向
先比较成绩。
如果两人的成绩相同，还缺哪个条件才能决定顺序？
提示 2：推导与实现
比较函数先处理成绩不同的情况。
只有成绩相同，才比较姓名的字典序。
知识补充
字符串用<比较的是字典序，不是长度。
例如"Li" < "Liu"，前面的字符相同且一个是另一个的前缀时，短的在前。
两种代码使用同一个比较规则，区别只在排序过程。
常见错误
成绩降序、姓名升序，两个方向不同。
比较函数不要写>=，相同记录不能互相排在对方前面。
只交换成绩会让姓名和成绩错位，要交换整个结构体。
自测
输入：
预期输出：
输入：1 Lin 0 → 预期输出：Lin 0
方法一：结构体与sort
#include <bits/stdc++.h>
using namespace std;
struct node {
string name;
int score;
} a[30];
bool cmp(node x, node y) {
if (x.score != y.score) return x.score > y.score;
return x.name < y.name;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i].name >> a[i].score;
sort(a, a + n, cmp);
for (int i = 0; i < n; i++) cout << a[i].name << ' ' << a[i].score << '\n';
return 0;
}
方法二：结构体与冒泡排序
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
struct node {
string name;
int score;
} a[N];
bool cmp(node x, node y) {
if (x.score != y.score) return x.score > y.score;
return x.name < y.name;
}
int n;
void bubble_sort() {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (cmp(a[j + 1], a[j]))
swap(a[j], a[j + 1]);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i].name >> a[i].score;
bubble_sort();
for (int i = 0; i < n; i++) cout << a[i].name << ' ' << a[i].score << '\n';
return 0;
}
1183：病人排队¶
提示 1：找方向
先别急着把所有人按年龄排序。
不到60岁的人，也需要按年龄重新排吗？
提示 2：推导与实现
把病人分成老年人和其他人两组。
老年人比较年龄，相同再比较登记顺序；另一组保留原顺序。
知识补充
用输入时的下标记录登记顺序，数值小的先登记。
sort不保证同龄病人保留原顺序，所以要在比较函数中补上登记顺序。
常见错误
60岁属于老年人，分组条件是>= 60。
老年人同龄时按登记先后排，不是按编号大小排。
编号用string保存，避免丢掉前导零。
自测
输入：
预期输出：
输入：1 007 60 → 预期输出：007
自己试试：把第一组中001的年龄改为60，先重新写出排队顺序，再运行。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
struct node1 {
int year;
int id;
string num;
} A[N];
bool cmp(node1 x, node1 y) {
if (x.year != y.year) return x.year > y.year;
return x.id < y.id;
}
string B[N];
int k1, k2;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string x;
int y;
cin >> x >> y;
if (y >= 60) {
A[k1].id = i;
A[k1].year = y;
A[k1].num = x;
k1++;
} else B[k2++] = x;
}
sort(A, A + k1, cmp);
for (int i = 0; i < k1; i++) cout << A[i].num << '\n';
for (int i = 0; i < k2; i++) cout << B[i] << '\n';
return 0;
}
1839：【05NOIP 提高组】谁拿了最多奖学金¶
提示 1：找方向
一个人能同时获得几种奖学金？
先给一名学生逐项判断，再考虑所有学生。
提示 2：推导与实现
每项符合条件的奖金都要累加。
维护个人最高金额和全体总金额，相同最高金额保留先出现的人。
知识补充
结构体中的score是期末平均成绩，review是班级评议成绩。
cadre、west分别表示是否为学生干部、是否来自西部，paper是论文数。
方法一先保存记录，再用calc计算每人的奖金；方法二边读边算，不保存所有记录。
常见错误
五项奖励彼此独立，不能写成if ... else if ...。
“高于”用>，80、85、90这些边界要逐项核对。
干部标记和西部标记别读反，比较字符用'Y'。
奖金相同不替换答案，更新条件用>。
自测
输入：
预期输出：
输入：
预期输出：
方法一：结构体记录与函数计算
#include <bits/stdc++.h>
using namespace std;
struct node {
string name;
int score, review;
char cadre, west;
int paper, money;
} a[110];
int calc(node x) {
int sum = 0;
if (x.score > 80 && x.paper >= 1) sum += 8000;
if (x.score > 85 && x.review > 80) sum += 4000;
if (x.score > 90) sum += 2000;
if (x.score > 85 && x.west == 'Y') sum += 1000;
if (x.review > 80 && x.cadre == 'Y') sum += 850;
return sum;
}
int main() {
int n, sum = 0, idx = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].name >> a[i].score >> a[i].review;
cin >> a[i].cadre >> a[i].west >> a[i].paper;
}
for (int i = 0; i < n; i++) {
a[i].money = calc(a[i]);
sum += a[i].money;
if (a[i].money > a[idx].money) idx = i;
}
cout << a[idx].name << '\n' << a[idx].money << '\n' << sum;
return 0;
}
方法二：边读边计算
#include <bits/stdc++.h>
using namespace std;
int n;
string top;
int maxn = -1;
int sum;
int main() {
cin >> n;
while (n--) {
string s;
int pingjun, pingyi;
char ganbu, xibu;
int lunwen;
cin >> s >> pingjun >> pingyi >> ganbu >> xibu >> lunwen;
int now = 0;
if (pingjun > 80 && lunwen >= 1) now += 8000;
if (pingjun > 85 && pingyi > 80) now += 4000;
if (pingjun > 90) now += 2000;
if (pingjun > 85 && xibu == 'Y') now += 1000;
if (pingyi > 80 && ganbu == 'Y') now += 850;
if (now > maxn) {
maxn = now;
top = s;
}
sum += now;
}
cout << top << '\n' << maxn << '\n' << sum;
return 0;
}