PAT甲级1012.

目录

A1012

题目

样例

输入:

5 6
310101 98 85 88
310102 70 95 88
310103 82 87 94
310104 91 91 91
310105 85 90 90
310101
310102
310103
310104
310105
999999

输出:

1 C
1 M
1 E
1 A
3 A
N/A

思路和坑点

　　对各个成绩进行排名，并且按照怕排名更新rank。同时使用map标记是否有记录存在，由于学生结构体的数据量比较大，所以采用排下标的方式，节省时间。另外，由于成绩只有三科，所以平均分的比较直接算成总分比较，可以有效避免平均以后浮点数比较的坑。
　　结构体下标排序参见我的博客分类PAT中的《PAT总结》中结构体部分的说明。排序的比较函数写成一个，使用全局变量标记控制排序规则。
　　坑点
　　PAT中的所有的排名方式大多是按照一下规则，并列时同排名，不并列时，排名是实际的次序，而不是紧跟并列的排名。比如：1 1 2 3 4，有前两个并列的情况，PAT中普遍采用的方法是1 1 3 4 5.　　

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{                //学生结构体 
    int id,c,m,e,a;                    //成绩 
    int ar,cr,mr,er;                //排名 
}Node;
vector<Node> ST;
map<int,int> mp;                    //记录是否存在该记录 
vector<int> sidx;                    //结构体数据量较大，使用下标排序，减少时间 
char tag;    
bool cmp(int i,int j){                //比较函数，使用全局标记控制 
    switch(tag){
        case 'A' :return ST[i].a>ST[j].a;break;
        case 'C' :return ST[i].c>ST[j].c;break;
        case 'M' :return ST[i].m>ST[j].m;break;
        case 'E' :return ST[i].e>ST[j].e;break;
    }
}
void check(){
    int id;
    scanf("%d",&id);                            //输出结果 
    if(mp.find(id)==mp.end())    puts("N/A");
    else{
        int v=mp[id];
        int rank=ST[v].er; char ch='E';            //根据优先级，由低到高进行比较，节省比较次数 
        if(ST[v].mr<=rank)        {rank=ST[v].mr;ch='M';} 
        if(ST[v].cr<=rank)        {rank=ST[v].cr;ch='C';} 
        if(ST[v].ar<=rank)        {rank=ST[v].ar;ch='A';} 
        printf("%d %c\n",rank,ch);
    }
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,k;
    scanf("%d%d",&n,&k);
    ST.resize(n);    sidx.resize(n);
    for(int i=0;i<n;i++){
        scanf("%d%d%d%d",&ST[i].id,&ST[i].c,&ST[i].m,&ST[i].e);
        mp[ST[i].id]=i;    sidx[i]=i;
        ST[i].a=ST[i].c+ST[i].m+ST[i].e;
    }
    tag='A';
    sort(sidx.begin(),sidx.end(),cmp);                    //排序 
    int pre=sidx[0];    ST[pre].ar=1;                    //初始化第一个排名 
    for(int i=1;i<n;i++){
        int v=sidx[i];                                    //后序排名由上一个决定，分数相同，排名相同 
        if(ST[v].a==ST[pre].a)    ST[v].ar=ST[pre].ar;
        else    ST[v].ar=i+1;                            //如果不同，更新为排名 
        pre=v; 
    }
    tag='C';
    sort(sidx.begin(),sidx.end(),cmp);
    pre=sidx[0];    ST[pre].cr=1;
    for(int i=1;i<n;i++){
        int v=sidx[i];
        if(ST[v].c==ST[pre].c)    ST[v].cr=ST[pre].cr;
        else    ST[v].cr=i+1;
        pre=v;
    }
    tag='M';
    sort(sidx.begin(),sidx.end(),cmp);
    pre=sidx[0];    ST[pre].mr=1;
    for(int i=1;i<n;i++){
        int v=sidx[i];
        if(ST[v].m==ST[pre].m)    ST[v].mr=ST[pre].mr;
        else    ST[v].mr=i+1;
        pre=v;
    }
    tag='E';
    sort(sidx.begin(),sidx.end(),cmp);
    pre=sidx[0];    ST[pre].er=1;
    for(int i=1;i<n;i++){
        int v=sidx[i];
        if(ST[v].e==ST[pre].e)    ST[v].er=ST[pre].er;
        else    ST[v].er=i+1;
        pre=v;
    }
    for(int i=0;i<k;i++){
        check();
    }
    return 0;
}