PAT甲级1075.

目录

A1075

题目

样例

输入:

7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0

输出:

1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -

思路和坑点

　　对于每一个学生使用结构体存储，对于其成绩，使用数组表示并初始化为-2，表示未提交过，-1表示未通过编译。依次读取成绩的提交记录，每次如果有更高的成绩，则更新成绩。然后遍历并统计计算学生的各项参数，最后排序并输出。
　　主要的难点在于数据的处理：成绩的更新，统计和输出、不需要输出的删选、排序规则。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int id,total=0,tag=0,cnt=0;    //id，total总分，tag为是否输出的标记，1表示需要输出，cnt为完美解题计数 
    int score[6];                   //成绩记录数组，初始化为-2，表示未提交过 
    node(){
        for(int i=1;i<=5;i++)
            score[i]=-2;
    }
}Node;
vector<Node> v;                     //存放数据 
vector<int> sid;                    //用于下标排序 
bool cmp(int i,int j){              //排序函数 
    if(v[i].tag!=v[j].tag) return v[i].tag>v[j].tag;                //需要输出的在前 
    else if(v[i].total!=v[j].total) return v[i].total>v[j].total;    //总成绩从高到底 
    else if(v[i].cnt!=v[j].cnt) return v[i].cnt>v[j].cnt;            //cnt从高到底 
    else  return v[i].id<v[j].id;                                    //id从低到高 
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,m,k;
    scanf("%d%d%d",&n,&k,&m);               //读入数据，并初始化每一个容器的大小 
    vector<int> p(k+1);                     //记录每题的分值 
    v.resize(n+1);    sid.resize(n+1);
    for(int i=1;i<=k;i++)                   //读入各题分值 
        scanf("%d",&p[i]);
    for(int i=0;i<m;i++){                   //读入每次提交 
        int id,index,s;    
        scanf("%d%d%d",&id,&index,&s);
        if(s>v[id].score[index])            //如果成绩更高则更新 
            v[id].score[index]=s;
    } 
    for(int i=1;i<=n;i++){                  //处理并统计每位学生的成绩信息 
        sid[i]=i;                           //初始化下标排序数组 
        v[i].id=i;                          //初始化每一个学生的id 
        for(int j=1;j<=k;j++){
            if(v[i].score[j]>=0){           //如果有提交过则tag标记为1 
                v[i].tag=1;                
                v[i].total+=v[i].score[j];  //成绩总分累加 
                if(v[i].score[j]==p[j])     //如果完美解题，cnt计数加一 
                    v[i].cnt++;
            }
        }
    }
    sort(sid.begin()+1,sid.end(),cmp);      //排序 
    int rank,pre;                           //rank为排名 ，pre用于记录前一个记录的下标 
    for(int i=1;i<=n;i++){            
        int l=sid[i];                       //读取当前的学生下标 
        if(v[l].tag==0) break;              //如果不需要输出，则返回（因为排完序之后，不需要输出的都在后边） 
        if(i==1) rank=1;                    //第一个rank为1 
        else if(v[l].total!=v[pre].total) rank=i;        //如果总成绩和前一个人不同，rank=i，否则和前一个人同排名 
        printf("%d %05d %d",rank,v[l].id,v[l].total);    //输出结果 
        for(int j=1;j<=k;j++){                           //输入每一题的成绩 
            switch(v[l].score[j]){    
                case -2: printf(" -");break;             //未提交为 - 
                case -1: printf(" 0");break;             //未通过编译为0 
                default: printf(" %d",v[l].score[j]);break;
            }
        }
        putchar('\n');
        pre=l;                              //更新pre 
    }
    return 0;
}