b158 - NOIP2007 1.奖学金
題目描述
題目要求根據學生的语文、数学、英语成绩，選出總分最高的五名學生，並按照總分、语文成绩、学号的顺序输出他们的学号和总分。
解題思路
此题的核心在于对学生数据进行排序。首先，定义一个结构体 grade 来存储每个学生的学号、语文成绩、数学成绩和英语成绩。然后，编写一个比较函数 cmp，该函数按照以下规则对学生进行排序：
- 首先，按照总分从高到低排序。
- 如果总分相同，则按照语文成绩从高到低排序。
- 如果总分和语文成绩都相同，则按照学号从小到大排序。
最后，使用
sort函数对学生数据进行排序，并输出前五名学生的学号和总分。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是学生人数。这是因为
sort函数的时间复杂度为 O(n log n)。 - 空間複雜度: O(n)，用于存储学生数据。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct grade{
int NO;
int ch;
int ma;
int ec;
};
bool cmp(grade a,grade b){
if(a.ch+a.ec+a.ma>b.ch+b.ec+b.ma)
return 1;
else if(a.ch+a.ec+a.ma==b.ch+b.ec+b.ma){
if(a.ch>b.ch)
return 1;
else if(a.ch==b.ch&&a.NO<b.NO)
return 1;
}
return 0;
}
int main(){
int a;
while(cin >> a){
grade b[a];
for(int i=0;i<a;i++){
cin >> b[i].ch >> b[i].ec >> b[i].ma;
b[i].NO=i+1;
}
sort(b,b+a,cmp);
for(int i=0;i<5;i++)
cout << b[i].NO <<" " <<b[i].ch+b[i].ec+b[i].ma<< "\n";
}
}