题目描述
现在,要给 CS 专业一年级的学生进行成绩评估。
我们只考虑他们的三门成绩:C–c语言,M–数学,E–英语,除此之外,我们还会考虑 A –三门成绩平均值。
注意:平均成绩为三科成绩平均值四舍五入取整的结果。
例如,四个学生的成绩单如下:
StudentID C M E A
310101 98 85 88 90
310102 70 95 88 84
310103 82 87 94 88
310104 91 91 91 91
每个学生都会有各科排名以及平均成绩排名,我们通过强调学生的最佳成绩来鼓励学生。
因此,每个学生的成绩单上只会有四个成绩中排名最高的那个成绩的排名,以及具体是哪项成绩(C、M、E、A 中的一项)。
例如,第一个学生的成绩单上会显示 1 C,因为他的C语言排名第 1,这是他的最佳名次。
而第四个学生的成绩单上会显示 1 A,因为他的平均成绩排名第 1,这是他的最佳名次。
输入格式
第一行包含两个整数 N,M,分别表示学生总数和查询成绩单次数。
接下来 N 行,每行首先包含一个由六位数字组成的学生 ID,然后包含三个整数分别表示该学生的 C,M,E 三科成绩。
接下来 M 行,每行包含一个学生 ID,表示要查询该学生的成绩单。
输出格式
对于每个学生,输出他的最佳排名以及该排名对应的是哪项成绩。
当多项排名相同,且都为最佳时,按照 A>C>M>E 的优先级,选择输出哪项成绩。
如果无法查询到该学生的成绩,则输出 N/A。
数据范围
1≤N,M≤2000,
每科成绩均在 [0,100] 之间。
样例
输入样例:
5 6
310101 98 85 88
310102 70 95 88
310103 82 87 94
310104 91 91 91
310105 85 90 90
310101
310102
310103
310104
310105
999999
输出样例:
1 C
1 M
1 E
1 A
3 A
N/A
算法1
(二分+结构体排序) $O(n^2)$
难点在于二分条件要写对
记住四舍五入使用round
floor()不大于自变量的最大整数
cell()不小于自自变量的最小整数
然后刚开始在算平均成绩的时候,没有用double,导致wa了,注意这些细节
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
typedef struct
{
int id;
int c,m,e;
int a;
int cr,mr,er,ar;
}CS;
CS stu[N];
bool cmpid(CS a,CS b)
{
return a.id<b.id;
}
bool cmpc(CS a,CS b)
{
return a.c>b.c;
}
bool cmpm(CS a,CS b)
{
return a.m>b.m;
}
bool cmpe(CS a,CS b)
{
return a.e>b.e;
}
bool cmpa(CS a,CS b)
{
return a.a>b.a;
}
int n,m;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>stu[i].id>>stu[i].c>>stu[i].m>>stu[i].e;
stu[i].a=round((stu[i].c+stu[i].m+stu[i].e)/3.0);
}
sort(stu,stu+n,cmpc);//按照c语言排序
for(int i=0;i<n;i++)stu[i].cr=i+1;
for(int i=1;i<n;i++)
{
if(stu[i].c==stu[i-1].c)stu[i].cr=stu[i-1].cr;
}
sort(stu,stu+n,cmpm);//按照数学排序
for(int i=0;i<n;i++)stu[i].mr=i+1;
for(int i=1;i<n;i++)
{
if(stu[i].m==stu[i-1].m)stu[i].mr=stu[i-1].mr;
}
sort(stu,stu+n,cmpe);//按照英语成绩排序
for(int i=0;i<n;i++)stu[i].er=i+1;
for(int i=1;i<n;i++)
{
if(stu[i].e==stu[i-1].e)stu[i].er=stu[i-1].er;
}
sort(stu,stu+n,cmpa);//按照加权成绩排序
for(int i=0;i<n;i++)stu[i].ar=i+1;
for(int i=1;i<n;i++)
{
if(stu[i].a==stu[i-1].a)stu[i].ar=stu[i-1].ar;
}
sort(stu,stu+n,cmpid);
while(m--)
{
int id;
cin>>id;
int l=0,r=n;
while(l<r)
{
int mid=(l+r)/2;
if(stu[mid].id>=id)r=mid;
else l=mid+1;
}
if(stu[l].id!=id)cout<<"N/A"<<endl;
else
{
int er=stu[l].er,ar=stu[l].ar,cr=stu[l].cr,mr=stu[l].mr;
if(ar<=er&&ar<=mr&&ar<=cr)cout<<ar<<" A"<<endl;
else if(cr<=mr&&cr<=er&&cr<=ar)cout<<cr<<" C"<<endl;
else if(mr<=ar&&mr<=cr&&mr<=er)cout<<mr<<" M"<<endl;
else cout<<er<<" E"<<endl;
}
}
return 0;
}