A1012 The Best Rank (25分)

考察：多个维度的排序（二维数组解决）

learn && wrong:
1、ID可以不用字符，而用int，因为只有6位，并且，6位的话，结果提数组要开到6位1000001以上
2、以数组下标做排名，第一个置位1，循环从1开始
3、取平均数用round（）函数是在数学库，要求浮点型

/*
题意：
1、首先，n个考生n个排名，接下来有m个查询，输出排名最高的学科，
2、如果不同的学科有相同的排名，则按优先级A>C>M>E输出，如果查询ID不在，则输出N/A

编程思想：
1、首先怎么排序呢？排序倒是简单，但是如何分类呢，我要开四个结构体数组
2、然后分别排序，然后比较

这样不对！真确
1、结构体数组，一个学号，一个包含四个int的结构体数组
2、读入ID和3个分数，并计算第一个平均分
3、用sort函数枚举A\C\M\E,排序，并在rank数组中记录排名
4、在查询时，输入ID，扫描所有rank[id][0]~rank[id][3]，找出排名最高的
*/

错误的写法
/*
#include <iostream>
#include <string>


using namespace std;

bool cmp(student a, student b) {
    return a.score > b.score;
}

struct student {
    string id;
    char flag;
    int score;
}student_A[2001], student_C[2001], student_M[2001], student_E[2001];

int average（int c, int m, int e){
    int average = (c + m + e) / 3;
    return average;
}

int main()
{
    int n, m;
    char id[7];
    cin >> n >> m;
    for (int i = 0;i < n;i++) {
        cin >>student_A.id >>student_C->score >> student_M->score >> student_E.score;  //如果这么多数组，每一个都要复制一个ID的，这样时间复杂度太高了，我觉得应该是四个聚集在一起
        student_A = average(student_C.score, student_M.score, student_E.score);
    }

    sort(student_A, student_A + n);
    sort(student_C, student_C + n);
    sort(student_M, student_M + n);
    sort(student_E, student_E + n);

    for (itn j = 0;j < m;j++) {
        
    }
}

*/

正确答案
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

struct student {
    int id; //存放6位整数的ID
    int grade[4]; //存放四个分数
}stu[2010];

char course[4] = { 'A', 'C', 'M', 'E' }; //按优先级顺序，方便输出
int rank1[10000000][4] = { 0 }; //rand[id][0]~rank[id][4]为4门课对应的排名  (!!!)为什么要1W
int now; //cmp函数中国能使用，表示当前按now号分数排序stu数组

bool cmp(student a, student b) {
    return a.grade[now] > b.grade[now];
}

int main() {
    int n, m;
    scanf_s("%d%d", &n, &m);

    //读入分数，其中grade[0]~grade[3]分别代表A、C、M、E

    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] = round((stu[i].grade[1] + stu[i].grade[2] + stu[i].grade[3])) / 3.0 + 0.5; // (!!!)
    }

    for (now = 0; now < 4;now++) {  //枚举A、C、M、E，4个中的一个   (111)整个循环，用一个二维数组来存放排名真的掉
        sort(stu, stu + n,cmp);    //对所有考生按该分数从大到小排序
        rank1[stu[0].id][now] = 1; //排序万，将分数最高的设为rank1

        for (int i = 1;i < n;i++) {  //对剩下的考生  
            if (stu[i].grade[now] == stu[i - 1].grade[now]) {
                rank1[stu[i].id][now] = rank1[stu[i - 1].id][now]; //若与前一位考生分数相同，则排名相同
            }
            else {
                rank1[stu[i].id][now] = i + 1; //否则，设置正确的排名
            }

        }
    }

    int query; //查询的考生ID
    for (int i = 0;i < m;i++) {
        cin >> query;
        if (rank1[query][0] == 0) {  //排序，由大到小，如果是0，说明没有数据
            printf("N/A\n");
        }
        else {
            int k = 0;  //选出rank[query][0~3]中最小的rank,rank值越小，排名越高
            for (int j = 0;j < 4;j++) {
                if (rank1[query][j] < rank1[query][k]) { //找最小的果然没变，还是得枚举
                    k = j;
                }
            }
            printf("%d %c\n", rank1[query][k], course[k]);
        }
    }
    return 0;
}