C++：问题C:网课排序-创新互联

记录一道排序问题的思考

网课终于结束了。
很多同学也回到学校上课了。
HZSjYJ决定对网课上的好的前五名的学校进行奖励和宣传。他们挑选了语文数学英语三门课，并对每个学校三门课进行了打分。
当然奖励排名规则如下：
1 三门课总分高的排在前面
2 总分相同，则语文高的排在前面
3 如果总分和语文都相同，则序号在前的排在前面（序号是JYJ事先定好的，就是输入顺序）

第一行输入一个整数n,表示学校数
然后是n行，每行3个数字，分别代表1个学校的语文数学英语的打分

输出5行，分别是排名前5的学校（按照排名输出），每行2个整数，为序号和总分

输入

6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出

6 265
4 264
3 258
2 244
1 237

这道题当然可以基于排序去做，写一个快排，然后改变其中排序的逻辑，但是这样做的话就要对整个输入的数组进行存储和排序，因为这里只要前几名的一个排序结果，所以不妨使用另外一种思路来解决这类问题

只存储前几名，每次只和前几名进行比较

#includeusing namespace std;
int main(){int n;
	int tl[6]={0},ch[6]={0},ID[6]={0};
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout)  ;                                                                                                            
	cin>>n;	
	for(int i=0;iint totals,x,y,z;
		cin>>x>>y>>z;
		tl[5]=x+y+z; ch[5]=x;	ID[5]=i+1;
		for(int j=4;j>=0;j--){	if(tl[j]<=tl[j+1]){		if(tl[j+1]>tl[j] ||(tl[j]==tl[j+1] && ch[j+1]>ch[j] ))
				{int temp;
					temp=tl[j];tl[j]=tl[j+1];tl[j+1]=temp;
					temp=ch[j];ch[j]=ch[j+1];ch[j+1]=temp;
					temp=ID[j];ID[j]=ID[j+1];ID[j+1]=temp;					
				}
			}
			else break;
		}				
	}	
	
	for(int i=0;i<5;i++)
		cout<

时间复杂度：O(n)
空间复杂度：O(1)