《聪明人的游戏 信息学探秘.提高篇》 第四章 简单排序(C++) 第2课 考试排名——插入排序（Score）
【问题描述】
桐桐的学校刚刚举行了期中考试，桐桐所在的七年级一共考了五个科目：语文、数学、英语、政治和历史。现在所有成绩都已经出来，班主任找到了桐桐，想让桐桐帮忙计算班里所有同学的五科总成绩，并按照总成绩由高到低的顺序排名，如果两个学生的总成绩相同，则学号小的排在前面。你能够编写程序帮助桐桐完成任务吗？
【输入格式】
第1行：一个数n(1≤n<100)，表示桐桐所在班级的学生数；
第2行至第n+1行：第i行表示学号为i-1的学生的成绩（全部是整数，范围在O到1 00之间），每行有5个数，分别表示当前学生的五科成绩，相邻数之间用一个空格隔开。
【输出格式】
只有1行，按总成绩由高到低的顺序输出对应学生的学号，相邻学号间用一个空格隔开。
【输入样例】
5
89 76 80 67 90
70 80 78 95 92
65 77 88 98 100
82 68 99 87 69
100 92 87 79 90
【输出样例】
5 3 2 4 1
/*
第2课 考试排名——插入排序（Score）02
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=102;
int n;
struct data
{
//学号
int num;
//总成绩
int total;
}a[maxn];
void init()
{
int n1,n2,n3,n4,n5;
cin>>n;
for(int i=1;i<=n;++i)
{
//输入每科的成绩
cin>>n1>>n2>>n3>>n4>>n5;
//存储总成绩
a[i].total=n1+n2+n3+n4+n5;
//存储学号
a[i].num=i;
cout<<"i="<<a[i].total<<" "<<a[i].num<<endl;
}
cout<<"*****************************"<<endl;
}
void print( )
{
//按总成绩由高到低的顺序输出对应学生的学号，
//相邻学号间用一个空格隔开。
for(int i=1;i<=n;i++)
{
cout<<a[i].num<<" "<<a[i].total<<endl;
}
cout<<endl;
}
void work()
{
int j;
data temp;
for(int i=2;i<=n;i++)
{
cout<<"i="<<i<<endl;
temp.total=a[i].total;
temp.num=a[i].num;
cout<<"i="<<i<<" "<<temp.total<<" "<<temp.num<<endl;
j=i;
/*
402 415 428 405 448
402 415 428 428 448
448 428 415 405 402
*/
while(a[j-1].total>temp.total && j>1)
{
a[j].total=a[j-1].total;
a[j].num=a[j-1].num;
cout<<"j="<<j<<" "<<a[j].total<<" "<<a[j].num<<endl;
j--;
}
a[j].total=temp.total;
a[j].num=temp.num;
cout<<"j="<<j<<" "<<a[j].total<<" "<<a[j].num<<endl;
print();
cout<<"------------------------------"<<endl;
}
}
void print_num( )
{
//按总成绩由高到低的顺序输出对应学生的学号，
//相邻学号间用一个空格隔开。
for(int i=n;i>=1;--i)
{
cout<<a[i].num<<" ";
}
cout<<endl;
}
int main( void )
{
init();//初始化
work();//插入排序
print_num();//输出
return 0;
}
/*
[初始关键字]
i=1 [49]38 65 97 76 13 27 49
i=2 (38) [38 49]65 97 76 13 27 49
i=3 (65) [38 49 65]97 76 13 27 49
i=4 (97) [38 49 65 97]76 13 27 49
i=5 (76) [38 49 65 76 97]13 27 49
i=6 (13) [13 38 49 65 76 97]27 49
i=7 (27) [13 27 38 49 65 76 97]49
i=8 (49) [13 27 38 49 49 65 76 97]
5
89 76 80 67 90
70 80 78 95 92
65 77 88 98 100
82 68 99 87 69
100 92 87 79 90
【输出样例】
5 3 2 4 1
*/
桐桐的学校刚刚举行了期中考试，桐桐所在的七年级一共考了五个科目：语文、数学、英语、政治和历史。现在所有成绩都已经出来，班主任找到了桐桐，想让桐桐帮忙计算班里所有同学的五科总成绩，并按照总成绩由高到低的顺序排名，如果两个学生的总成绩相同，则学号小的排在前面。你能够编写程序帮助桐桐完成任务吗？
【输入格式】
第1行：一个数n(1≤n<100)，表示桐桐所在班级的学生数；
第2行至第n+1行：第i行表示学号为i-1的学生的成绩（全部是整数，范围在O到1 00之间），每行有5个数，分别表示当前学生的五科成绩，相邻数之间用一个空格隔开。
【输出格式】
只有1行，按总成绩由高到低的顺序输出对应学生的学号，相邻学号间用一个空格隔开。
【输入样例】
5
89 76 80 67 90
70 80 78 95 92
65 77 88 98 100
82 68 99 87 69
100 92 87 79 90
【输出样例】
5 3 2 4 1
/*
第2课 考试排名——插入排序（Score）02
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=102;
int n;
struct data
{
//学号
int num;
//总成绩
int total;
}a[maxn];
void init()
{
int n1,n2,n3,n4,n5;
cin>>n;
for(int i=1;i<=n;++i)
{
//输入每科的成绩
cin>>n1>>n2>>n3>>n4>>n5;
//存储总成绩
a[i].total=n1+n2+n3+n4+n5;
//存储学号
a[i].num=i;
cout<<"i="<<a[i].total<<" "<<a[i].num<<endl;
}
cout<<"*****************************"<<endl;
}
void print( )
{
//按总成绩由高到低的顺序输出对应学生的学号，
//相邻学号间用一个空格隔开。
for(int i=1;i<=n;i++)
{
cout<<a[i].num<<" "<<a[i].total<<endl;
}
cout<<endl;
}
void work()
{
int j;
data temp;
for(int i=2;i<=n;i++)
{
cout<<"i="<<i<<endl;
temp.total=a[i].total;
temp.num=a[i].num;
cout<<"i="<<i<<" "<<temp.total<<" "<<temp.num<<endl;
j=i;
/*
402 415 428 405 448
402 415 428 428 448
448 428 415 405 402
*/
while(a[j-1].total>temp.total && j>1)
{
a[j].total=a[j-1].total;
a[j].num=a[j-1].num;
cout<<"j="<<j<<" "<<a[j].total<<" "<<a[j].num<<endl;
j--;
}
a[j].total=temp.total;
a[j].num=temp.num;
cout<<"j="<<j<<" "<<a[j].total<<" "<<a[j].num<<endl;
print();
cout<<"------------------------------"<<endl;
}
}
void print_num( )
{
//按总成绩由高到低的顺序输出对应学生的学号，
//相邻学号间用一个空格隔开。
for(int i=n;i>=1;--i)
{
cout<<a[i].num<<" ";
}
cout<<endl;
}
int main( void )
{
init();//初始化
work();//插入排序
print_num();//输出
return 0;
}
/*
[初始关键字]
i=1 [49]38 65 97 76 13 27 49
i=2 (38) [38 49]65 97 76 13 27 49
i=3 (65) [38 49 65]97 76 13 27 49
i=4 (97) [38 49 65 97]76 13 27 49
i=5 (76) [38 49 65 76 97]13 27 49
i=6 (13) [13 38 49 65 76 97]27 49
i=7 (27) [13 27 38 49 65 76 97]49
i=8 (49) [13 27 38 49 49 65 76 97]
5
89 76 80 67 90
70 80 78 95 92
65 77 88 98 100
82 68 99 87 69
100 92 87 79 90
【输出样例】
5 3 2 4 1
*/
