(奖学金算法)
2021/01/21
算法1
本题目的要求是:总成绩大小,语文成绩大小,学号的从小到大的顺序
1:前两个要求很容易让人想到pair<int,int>PII
,然后对其进行排序
2 :pair容器只支持两个参数。所以可以再新建一个 pair<PII,int>PIII
来存储两个成绩+学号
3 :问题:学号是要求从小到大的优先级?但是sort
函数是从大到小,所以需要取一个相反数。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int>PII;//总成绩,语文成绩//
typedef pair<PII,int>PIII;// 总成绩,语文成绩,学号
const int N = 310;
int p[N][4];
PII all_Chi[N];
PIII all_Chi_ID[N];
//给前5名学生颁发奖学金
int main(){
int n ;
cin >> n;
for(int i=0; i<n;i++){
cin >> p[i][0]>>p[i][1]>>p[i][2];
p[i][3] = p[i][0]+p[i][1]+p[i][2];
}
//在数组p[N][4]中,行号表示学号,第一列 语文 ,第二列 数学,第三列 英语, 第四列总成绩。
for(int i = 0; i<n; i++){
all_Chi[i]={p[i][3],p[i][0]};
all_Chi_ID[i]={all_Chi[i],-1*i};
}
sort(all_Chi_ID,all_Chi_ID+n);
for(int i = n-1;i>=n-5;i--)
cout << -1*all_Chi_ID[i].second+1<<" "<<all_Chi_ID[i].first.first << endl;
return 0;
}