[PAT解题报告] The Best Rank
简单题，输入是每个学生的id以及三门课程成绩，分别是C语言(C),数学(M)和英语(E),
三门课程成绩都是不超过100的非负整数。对每个学生，再求一个平均分（除以3，下取整），作为另外一个分数A。对每个学生按照“ACME”的顺序找到他最好的名次，例如某学生的平均分是第1名，
C是第2名，M是第3名，E是第4名，则对于他来讲最好是选择按照平均分排名。也就是说对每个学生选出对他最有利的那一维作为他排名的依据。查询排名的学生可能不存在，所以要用一个map保存所有id和真正编号(0..n
- 1)的对应关系。
题目没什么坑，我们可以对每个学生按照ACME分别排序，排序当然可以直接sort,因为范围只有0到100，我采用了计数排序，也就是统计一下分数>=0,
>= 1, >=2，... >=100分别有多少个，存在数组have[]里，如果某个学生是x分，则他的名次是(have[x
+ 1] + 1),因为have[x +
1]是比它高分的人的个数，注意have数组至少开到101。还有注意选择最高名次的顺序是按照ACME的顺序。
代码：
#include <cstdio>
#include <string>
#include <cstring>
#include <map>
using namespace std;
const char *c = "ACME";
int a[2002][4];
int have[102];
map<string,int> id;
char s[10000];
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0; i < n; ++i) {
scanf("%s%d%d%d",s,&a[i][1],&a[i][2],&a[i][3]);
a[i][0] = (a[i][1] + a[i][2] + a[i][3]) / 3;
id[s] = i;
}
for (int i = 0; i < 4; ++i) {
memset(have,0,sizeof(have));
for (int j = 0; j < n; ++j) {
++have[a[j][i]];
}
for (int j = 100; j >= 0; --j) {
have[j] += have[j + 1];
}
for (int j = 0; j < n; ++j) {
a[j][i] = have[a[j][i] + 1] + 1;
}
}
for (;m;--m) {
scanf("%s",s);
map<string,int>::iterator t = id.find(s);
if (t == id.end()) {
puts("N/A");
}
else {
int x = 0;
for (int i = 0; i < 4; ++i) {
if (a[t->second][i] < a[t->second][x]) {
x = i;
}
}
printf("%d %c\n",a[t->second][x], c[x]);
}
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1012
Momenta公司福利 282人发布
