信息学奥赛一本通 1179：奖学金 | 1938：【07NOIP普及组】奖学金 | OpenJudge NOI 1.10 04 | 洛谷 P1093 [NOIP2007 普及组] 奖学金

【题目链接】

ybt 1179：奖学金
ybt 1938：【07NOIP普及组】奖学金
OpenJudge NOI 1.10 04:奖学金
洛谷 P1093 [NOIP2007 普及组] 奖学金

【题目考点】

1. 排序

【君义精讲】排序算法

2. 多关键字排序

方法1：将多关键字的排序条件整合为单一排序条件
方法2：使用稳定的排序算法进行多趟排序

【解题思路】

设结构体表示学生信息，保存人名、学号及各科成绩

解法1：将多关键字的排序条件整合为单一排序条件

可以将该排序条件设为函数：函数传入两个学生的结构体对象a与b
如果a与b的总成绩及语文成绩相同，学号小的排在前面。
如果a与b的总成绩相同但语文成绩不同，语文成绩高的排在前面。
如果a与b的总成绩不同，总成绩高的排在前面。
当然，也可以将整个条件写为一个表达式。
排序方法可以任意选择。

解法2：使用稳定的排序算法进行多趟排序

先按学号从小到大排序
再按语文成绩从高到低排序
再按总成绩从高到低排序。
只能选择稳定的排序方法。

【题解代码】

解法1：将多关键字的排序条件整合为单一排序条件

• 函数写法1 + 插入排序

#include<bits/stdc++.h> using namespace std; struct Stu {int id, Chinese, score;//id:编号 Chinese:语文成绩 score:总成绩 }; bool isPrior(Stu d1, Stu d2)//比较函数 判断d1是否应该在d2前面 {if(d1.score > d2.score)//比较总分 return true;else if(d1.score < d2.score)return false;else//总分数相等 {if(d1.Chinese > d2.Chinese)//比较语文成绩 return true;else if(d1.Chinese < d2.Chinese)return false;else//语文成绩相等 {if(d1.id < d2.id)//比较学号 return true;elsereturn false;} } } int main() {int n, a, b, c;//n:人数 a,b,c：语文，数学，英语成绩cin >> n;Stu d[305]; for(int i = 1; i <= n; ++i){cin >> a >> b >> c;d[i].id = i;d[i].Chinese = a;d[i].score = a+b+c;}for(int i = 2; i <= n; ++i)//插入排序 {for(int j = i; j > 1; --j){if(isPrior(d[j], d[j-1]))swap(d[j], d[j-1]);elsebreak;}}for(int i = 1; i <= 5; ++i)cout << d[i].id << ' ' << d[i].score << endl;return 0; }

• 函数写法2 + STL sort函数排序

#include<bits/stdc++.h> using namespace std; struct Stu {int id, Chinese, score;//id:编号 Chinese:语文成绩 score:总成绩 }; bool cmp(Stu d1, Stu d2)//比较函数 判断d1是否应该在d2前面 {if(d1.score == d2.score && d1.Chinese == d2.Chinese)return d1.id < d2.id;else if(d1.score == d2.score)return d1.Chinese > d2.Chinese;elsereturn d1.score > d2.score; } int main() {int n, a, b, c;//n:人数 a,b,c：语文，数学，英语成绩cin >> n;Stu d[305]; for(int i = 1; i <= n; ++i){cin >> a >> b >> c;d[i].id = i;d[i].Chinese = a;d[i].score = a+b+c;}sort(d+1, d+1+n, cmp); for(int i = 1; i <= 5; ++i)cout << d[i].id << ' ' << d[i].score << endl;return 0; }

• 写成表达式 + 冒泡排序

#include<bits/stdc++.h> using namespace std; struct Stu {int id, Chinese, score;//id:编号 Chinese:语文成绩 score:总成绩 }; bool isPrior(Stu d1, Stu d2)//比较函数 判断d1是否应该在d2前面 {return d1.score > d2.score || d1.score == d2.score && d1.Chinese > d2.Chinese ||d1.score == d2.score && d1.Chinese == d2.Chinese && d1.id < d2.id; } int main() {int n, a, b, c;//n:人数 a,b,c：语文，数学，英语成绩cin >> n;Stu d[305]; for(int i = 1; i <= n; ++i){cin >> a >> b >> c;d[i].id = i;d[i].Chinese = a;d[i].score = a+b+c;}for(int i = 1; i <= n-1; ++i)//冒泡排序 for(int j = 1; j <= n-i; ++j)if(isPrior(d[j+1], d[j]))//如果d[j+1]应该在d[j]前面 swap(d[j], d[j+1]);for(int i = 1; i <= 5; ++i)cout << d[i].id << ' ' << d[i].score << endl;return 0; }

解法2：使用稳定的排序算法进行多趟排序

#include<bits/stdc++.h> using namespace std; struct Stu {int id, Chinese, score;//id:编号 Chinese:语文成绩 score:总成绩 }; bool cmp1(Stu d1, Stu d2) {return d1.id < d2.id; } bool cmp2(Stu d1, Stu d2) {return d1.Chinese > d2.Chinese; } bool cmp3(Stu d1, Stu d2) {return d1.score > d2.score; } int main() {int n, a, b, c;//n:人数 a,b,c：语文，数学，英语成绩cin >> n;Stu d[305]; for(int i = 1; i <= n; ++i){cin >> a >> b >> c;d[i].id = i;d[i].Chinese = a;d[i].score = a+b+c;}stable_sort(d+1, d+1+n, cmp1);//学号从小到大stable_sort(d+1, d+1+n, cmp2);//语文从大到小stable_sort(d+1, d+1+n, cmp3);//总分从大到小 for(int i = 1; i <= 5; ++i)cout << d[i].id << ' ' << d[i].score << endl;return 0; }

总结

以上是生活随笔为你收集整理的信息学奥赛一本通 1179：奖学金 | 1938：【07NOIP普及组】奖学金 | OpenJudge NOI 1.10 04 | 洛谷 P1093 [NOIP2007 普及组] 奖学金的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。