PAT (Advanced Level) 1012 The Best Rank (25 分)

序：
经典结构体+排序，不同的是这次要排四个，具体的操作有些繁琐

题目概述：
给出多个学生的各科成绩，当查询对应学生时，需要按一定的优先级输出该学生最高的排名以及对应的学科。

分析：
1.结构体建立的不叫复杂，包括四个分数和四个排名
2.exist的建立，快速判断查询是否命中，以及快速定位查询的目标，而不用遍历。（相当于牺牲存储换取速度）

//又来结构体+排序？
//这次更复杂

#include<bits/stdc++.h>
using namespace std;

struct student
{   
    int id;
    int c, m, e, a;
    int r1, r2, r3, r4;
    int bestr;
    char bestsub;
}stu[2021];

int exist[1000000];//快速判断是否有该id以及定位

bool cmp1(student stu1, student stu2) {return stu1.c > stu2.c;}
bool cmp2(student stu1, student stu2) {return stu1.m > stu2.m;}
bool cmp3(student stu1, student stu2) {return stu1.e > stu2.e;}
bool cmp4(student stu1, student stu2) {return stu1.a > stu2.a;}

int main()
{
    int N, M, id;
    scanf("%d%d", &N, &M);
    //录入分数
    for(int i = 0; i < N; i++)
    {
        scanf("%d", &stu[i].id);
        scanf("%d%d%d", &stu[i].c, &stu[i].m, &stu[i].e);
        stu[i].a = (stu[i].c + stu[i].m + stu[i].e) / 3 + 0.5;//四舍五入
    }
    //c进行排名
    sort(stu, stu + N, cmp1);
    
    stu[0].r1 = 1;
    for(int i = 1; i < N; i++)
    {
        if(stu[i].c == stu[i-1].c)
            stu[i].r1 = stu[i-1].r1;
        else stu[i].r1 = i + 1;
    }
    //m进行排名
    sort(stu, stu + N, cmp2);
    
    stu[0].r2 = 1;
    for(int i = 1; i < N; i++)
    {
        if(stu[i].m == stu[i-1].m)
            stu[i].r2 = stu[i-1].r2;
        else stu[i].r2 = i + 1;
    }    
    //e进行排名
    sort(stu, stu + N, cmp3);
    
    stu[0].r3 = 1;
    for(int i = 1; i < N; i++)
    {
        if(stu[i].e == stu[i-1].e)
            stu[i].r3 = stu[i-1].r3;
        else stu[i].r3 = i + 1;
    }     
    //a进行排名
    sort(stu, stu + N, cmp4);
    
    stu[0].r4 = 1;
    for(int i = 1; i < N; i++)
    {
        if(stu[i].a == stu[i-1].a)
            stu[i].r4 = stu[i-1].r4;
        else stu[i].r4 = i + 1;
    }    
    //得出每个人的最好排名和科目
    for(int i = 0; i < N; i++)
    {
        stu[i].bestr = min(stu[i].r1, min(stu[i].r2, min(stu[i].r3, stu[i].r4)));
        if(stu[i].bestr == stu[i].r4) stu[i].bestsub = 'A';
        else if(stu[i].bestr == stu[i].r1) stu[i].bestsub = 'C';
        else if(stu[i].bestr == stu[i].r2) stu[i].bestsub = 'M';
        else stu[i].bestsub = 'E';
        exist[stu[i].id] = i + 1;
    }
    
    //进行查询
    for(int i = 0; i < M; i++)
    {
        int query;
        scanf("%d", &query);
        int index = exist[query];
        if(index)
            printf("%d %c\n", stu[index - 1].bestr, stu[index - 1].bestsub);
        else
            printf("N/A\n");
    }
    return 0;
}

总结：
1.复制相似的代码要注意改的仔细！！！
2.四舍五入加0.5
3.可以用exist优化查询以及快速查找（牺牲空间为代价）