PAT甲级1025.

目录

A1025

题目

样例

输入:

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85

输出:

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

思路和坑点

　　使用结构体的多级排序，每次排序后更新名次。这里采用了排下标的方法来减少时间花费，详情可以参加PAT总结中关于结构体部分的总结。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{                    //学生结构体 
    string id;
    int score,local,lr;
}Node;
vector<Node> v;
vector<int> idsort;                        //用于按照下标排序 
int tag=1;
bool cmp(int i,int j){                    //多级排序，tag=1时，优先按照考场排，然后确定考场排名 
    if(tag==1){
        if(v[i].local!=v[j].local) return v[i].local<v[j].local;
        else if(v[i].score!=v[j].score) return v[i].score>v[j].score;
        else     return v[i].id<v[j].id;
    }
    else{
        if(v[i].score!=v[j].score)    return v[i].score>v[j].score;
        else return v[i].id<v[j].id;    //tag不等于1时，采用总排名的规则 
    }
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,k,cnt=0;;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&k);
        for(int j=0;j<k;j++){
            Node temp;
            cin>>temp.id;
            scanf("%d",&temp.score);
            temp.local=i;
            idsort.push_back(cnt++);
            v.push_back(temp);
        }
    }
    sort(idsort.begin(),idsort.end(),cmp);    
    int pre=idsort[0]; v[pre].lr=1; cnt=1;        //第一个优先处理 ，cnt用于更新排名 
    for(int i=1;i<idsort.size();i++){
        int index=idsort[i];
        cnt++;
        if(v[index].local==v[pre].local){        //如果当前的与前边同一考场 
            if(v[index].score==v[pre].score)
                v[index].lr=v[pre].lr;
            else
                v[index].lr=cnt;
        }
        else{                                    //如果不同考场 
            v[index].lr=1;    cnt=1;
        }
        pre=index;
    }
    tag=0;
    sort(idsort.begin(),idsort.end(),cmp);        //总排名一遍输出，一遍确定名次 
    cnt=1;
    printf("%d\n",idsort.size());
    pre=idsort[0];
    cout<<v[pre].id<<' '<<1<<' '<<v[pre].local<<' '<<1<<'\n';
    for(int i=1;i<idsort.size();i++){
        int index=idsort[i];
        cout<<v[index].id<<' ';
        if(v[index].score!=v[pre].score)
            cnt=i+1;
        printf("%d %d %d\n",cnt,v[index].local,v[index].lr);
        pre=index;
    }
    return 0;
}