PAT甲题 1012 The Best Rank


刚刚1011题,输出的全错,我寻思20分的题不至于吧 ,纳闷了半天发现题目让输出的’W’,我写成了’w’,所以细心是个good quality。废话不多讲,下面我们来看1012题。

题意回顾:

输入规格:
首先在第一行给出两个小于等于2000的正整数N,M;
其次按照顺序给出N个学生的学号、c语言成绩、数学成绩、英语成绩(每行一位学生);
最后给出M个欲查询自己排名的学生的学号(每行一位)。
输出规格:
对于一位学生,他/她拥有c语言( C )、数学( M )、英语( E )、平均分( A )这四项成绩,意味着他在所有学生中分别拥有四个排名。对于需要查询自己排名的学生,如果他有排名,我们需输出他四项排名中的最高排名和对应学科,若存在不同学科排名相同,则遵循A > C > M > E的优先级;若查无此人,输出N/A。每位学生输出占一行。

个人解题思路:

1.定义一个学生的结构体,以结构体数组来存储所有学生的信息;
2.自定义排序sort(),以单科来对学生进行排序;
3.定义map<string,pair>对学生最优成绩进行存储,first存储学号,second存放pair类型,pair类型的first存放最好排名,second存放对应学科;
4.需按不同学科排序4次,每进行完一次排序,按排名遍历一次,比较此次是否最更优以决定是否存入map中;
5.按需要查询成绩的学生学号,依次在map中进行搜索,若能找到则输出相应信息,找不到则输出N/A。

注意点:

主要还是关于单科排名问题,举一个例子便可阐述清楚,有学生A、B、C,分数为98,98,95,A、B排名为1,C排名为3,虽是常识,但是我编写程序时由于被此题绕的晕头转向而忽略了,所以还是提醒一下。

代码:

#include<iostream>
#include<algorithm>
#include<map> 
using namespace std;
int no = 0;
struct Student
{
    char id[7] = "";
    int grade[4] = { 0,0,0,0 }; //分别存储A、C、M、E,按此顺序可很方便的解决优先级要求
};
bool cmp(Student a, Student b)  //自定义排序
{
     return a.grade[no] > b.grade[no];
}
int main()
{
   int N, M;
   cin >> N >> M;
   Student stu[N];
   for (int i = 0; i < N; i++)
   {
        cin >> stu[i].id >> stu[i].grade[1] >> stu[i].grade[2] >> stu[i].grade[3];
        stu[i].grade[0] = stu[i].grade[1] + stu[i].grade[2] + stu[i].grade[3]; //算总分和平均分一样,反正最后都是比排名
   }
   string check[M]; //查询的学生学号
   for (int i = 0; i < M; i++)
  	  cin >> check[i];
   map< string, pair<int, char> > mp;
   char c[4] = { 'A','C','M','E' };
   for (; no < 4; no++)
   {
      int last = 101, rank = 1, lastrank = 1;
      sort(stu, stu + N, cmp);    //进行排序
      for (int i = 0; i < N; i++, rank++)
      {
           if (stu[i].grade[no] != last) //rank和lastrank的作用就是解决我上述的注意点问题
      	      lastrank = rank;
           if (no == 0 || mp[stu[i].id].first > lastrank)  //第一次或者更优时存入
     	       mp[stu[i].id] = make_pair(lastrank, c[no]);
           last = stu[i].grade[no];
      }
   }
   map< string, pair<int, char> >::iterator it;
   for (int i = 0; i < M; i++)
   {
	  it = mp.find(check[i]);
	  it == mp.end() ? cout << "N/A" << endl : cout << it->second.first << " " << it->second.second << endl;  //it==mp.end()即表示未找到
   }
   return 0;
}

在做这题时,刚开始思路比较乱,总想着能不能用更简便的算法解题,结果越想越乱,然后还是老老实实进行四遍排序,老老实实的去遍历比较;所以如果存在不足,还请各位大佬不吝赐教。

原文地址:https://www.cnblogs.com/yuhan-blog/p/12309120.html