思路
1.将每个学生的id
与ACME成绩映射在一起,一开始考虑用结构体,但是后面要对每门课排序,不 太方便,所以应该用unordered_map<string, vector<int>> grades
, vector<int>
存的是四门课的成绩。
2 对四门课成绩排序。创建vector<int> course[4]
表示有4个vector<int>
, 每一个动态数组都存了那一门学科所有学生的成绩,course[0]
表A,course[1]
表B,course[2]
表C,course[3]
表D。 后续对这个vector<int>
排序,再利用二分,找最靠近100分的位置,就可以知道这个学生的单科成绩排第几名
二分
函数
四舍五入:round(1.23)
,头文件<cmath>
排序:sort()
; 头文件<algorithm>
,O(n*log)
查找字符串:hash.count("abc")
, 返回”abc”的个数
注
四门课成绩要加的时候要先初始化为0
#include <iostream>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
unordered_map<string, vector<int>> grade; //将学生的id,与ACME四门学科映射起来
vector<int> course[4]; //4个动态数组,分别表示ACME的每门学科所有学生的成绩
//在从小到大排的学科分数中找到最靠近右边的位置,二分
int get_rank(vector<int>&a, int x)
{
int l = 0, r = a.size()-1;
while (l < r)
{
int mid = l+r+1 >> 1;
if (a[mid] <= x) l = mid;
else r = mid-1;
}
return a.size()-r;
}
int main()
{
int n, m;
cin >> n >> m;
//输入学生的id,与CMEA四门课成绩
for (int i = 0; i < n; i++)
{
string id;
cin >> id;
int t[4] = {0}; //表这个学生的四门课,记得初始化为0
//输入这个学生的四门课
for (int j = 1; j < 4; j++) //从1 开始是因为排序按ACME,输入按CMEA
{
cin >> t[j];
t[0] += t[j];
}
t[0] = round(t[0]/3.0); //记得转为浮点数
//将每门课成绩分别加到对应grade与course里面去
for (int j = 0; j < 4; j++)
{
course[j].push_back(t[j]);
grade[id].push_back(t[j]);
}
}
//将每门课成绩从小到大排序
for (int i = 0; i < 4; i++)
sort(course[i].begin(), course[i].end());
//进行m 次查询
char name[] = "ACME";
while (m--)
{
string id;
cin >> id;
if (grade.count(id) == 0) puts("N/A");
else
{
int res = n + 1; //记录最大排名
char c; //记录最大排名的学科
//分别按优先级ACME遍历4门学科,找到最大排名
for (int i = 0; i < 4; i++)
{
int rank = get_rank(course[i], grade[id][i]);
//第一个参数:第几门学科,这个人的分数
if (rank < res)
{
res = rank;
c = name[i];
}
}
cout << res << " " << c << endl;
}
}
return 0;
}