[NOIP2007 普及组] 奖学金 题解

（一）读懂题目

关键句：期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
最后，让我们输出排在前五的学生的座号以及分数

（二）分析算法+时间复杂度和空间复杂度

算法：选择排序
时间复杂度：O(n*n)
空间复杂度：O(1)——虽然要存储很多学生，但还是常数项

（三）代码实现

#include<iostream>
#include<cstdio>
using namespace std;
int n,maxn=-1;//定义变量，有n个学生，maxn用来存储总分最大的人 
int a[305],b[305],c[305],d[305],e[305];//因为n小于300，设305个变量足矣 
int main(){cin>>n;//输入 for(int i=1;i<=n;i++)//输入 {cin>>a[i];//语文成绩 cin>>b[i];//数学成绩 cin>>c[i];//英语成绩 d[i]=a[i]+b[i]+c[i];//总分 e[i]=i;//学号 }for(int i=1;i<n;i++)//进行选择排序 {for(int j=i+1;j<=n;j++){if(d[i]<d[j])//先判断总分 {swap(d[i],d[j]);//交换总分 swap(a[i],a[j]);//交换语文成绩 swap(b[i],b[j]);//交换数学成绩 swap(c[i],c[j]);//交换英语成绩 swap(e[i],e[j]);//交换学号}if(d[i]==d[j])//如果总分一样 {if(a[i]<a[j])//看语文成绩 {swap(d[i],d[j]);//交换总分 swap(a[i],a[j]);//交换语文成绩 swap(b[i],b[j]);//交换数学成绩 swap(c[i],c[j]);//交换英语成绩swap(e[i],e[j]);//交换学号}if(a[i]==a[j])//如果语文成绩也一样 {if(e[i]>e[j])//看学号 {swap(d[i],d[j]);//交换总分 swap(a[i],a[j]);//交换语文成绩 swap(b[i],b[j]);//交换数学成绩swap(c[i],c[j]);//交换英语成绩swap(e[i],e[j]);//交换学号}}}}}for(int i=1;i<=5;i++)//输出前五 {cout<<e[i]<<" "<<d[i]<<endl;//输出学号和总分 }return 0;
}

（四）总结反思

本题虽然题目长了点，条件多了点，但毕竟万变不离其宗，考察的还是排序算法，对，就我之前发的。
本题我是选择了用选择排序，复杂度是n*n，在本题中并不算多，一遍AC过^_^