[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


全部评论

相关推荐

ohs的小木屋:比不少实习待遇高了
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
八股刚起步,看了javaguide,小林coding,还有面渣,感觉面渣是体验最好的,请问只看面渣够用吗,有不完善的需要补吗?
码农索隆:先背最基础的知识,然后理解情景题,现在面试大多数喜欢问情景题,更考验面试者的基础和临场发挥情况
点赞 评论 收藏
分享
评论
4
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务