乐趣区

关于算法-数据结构:PAT甲级1012-The-Best-Rank

jiezi
题目粗心：

现已知 N 个考生的 3 门课分数 C、M、E, 而均匀分数 A 能够由这 3 个分数失去。当初别离按这 4 个分数对 n 个考生从高到低排序，这样对每个考生来说，就会有 4 个排名且每个分数都会有一个排名。接下来会有 M 个查问，每个查问输出一个考生的 ID, 输入该考生 4 个排名中最高的那个排名及对应是 A、C、M、E 中的哪一个。如果对不同课程有雷同排名的状况，则按优先级 A >C>M>E 输入; 如果查问的考生 ID 不存在，则输入 N /A。

算法思路：

这里为了不便起见，应用总分代替均匀分数，每一个学生保留所有的分数曾经对应科目的排名信息，同时为了避免非法查问，应用 isExist 建设学生 ID 与学生的映射，因为要获取每一个学生所有科目排名中最好的排名，那么就得一一依照每一个科目的分数进行排序，而后获取对应科目的排名。属于惯例排序题目，这里应用数组存储分数纯正是为了防止写反复的代码。

留神点：
isExist 的初始化得在取得排名之后，因为输入最好排名的时候须要依据 isExist 获取对应的学生信息，其中就包含排名
提交后果:

AC 代码：
#include<cstdio>
#include<vector>
#include<algorithm>
#include<unordered_map>

using namespace std;

struct Student{
    int id;
    int scores[4];// A,C,M,E 的分数
    int rank[4];// 每一门科目的名次，顺次是 A >C>M>E
};

unordered_map<int,Student> isExist;// 用于判断查问的学生是否存在
char subject[4] = {'A','C','M','E'}; // 不便输入最初最高排名对于的科目

int course_index;// 示意以后须要排序的科目
bool cmp(Student a, Student b){return a.scores[course_index]>b.scores[course_index];
}

void printBestRank(int query) {Student student = isExist[query];
    int index = 0;
    // 获取最好的排名
    for (int i = 1; i < 4; ++i) {if(student.rank[i]<student.rank[index]){index = i;}
    }
    printf("%d %c\n",student.rank[index],subject[index]);
}

int main(){
    int N,M;// 学生人数，查问排名的学生人数
    scanf("%d %d",&N,&M);
    vector<Student> students;// 学生汇合
    Student stu;
    int c,m,e;
    for (int i = 0; i < N; ++i) {scanf("%d %d %d %d",&stu.id,&c,&m,&e);
        stu.scores[1] = c;
        stu.scores[2] = m;
        stu.scores[3] = e;
        stu.scores[0] = c+m+e;
        students.push_back(stu);
    }
    // 对所有科目进行排序
    for (course_index=0;course_index<4;++course_index){sort(students.begin(),students.end(),cmp);
        // 获取以后科目的排名
        for (int i = 0; i < N; ++i) {if (i==0){students[i].rank[course_index] = 1;
            } else if (students[i].scores[course_index] == students[i-1].scores[course_index]){students[i].rank[course_index] = students[i-1].rank[course_index];
            } else {students[i].rank[course_index] = i+1;
            }
        }
    }
    // 初始化 isExist, 这里得在获取完排名后在进行初始化 isExit，不然会呈现输入为正数的状况
    for (int j = 0; j < N; ++j) {isExist[students[j].id] = students[j];
    }
    // 开始查问
    int query;// 待查问学生的 id
    for (int k = 0; k < M; ++k) {scanf("%d",&query);
        if (isExist.find(query)==isExist.end()){
            // 不存在
            printf("N/A\n");
        } else{printBestRank(query);
        }
    }
    return 0;
}
退出移动版