数据结构/PTA-PTA排名汇总/结构体快排

 PAT排名汇总 (25分)

计算机程序设计能力考试(Programming Ability Test,简称PAT)旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力,科学的评价计算机程序设计人才,为企业选拔人才提供参考标准(网址http://www.patest.cn)。

每次考试会在若干个不同的考点同时举行,每个考点用局域网,产生本考点的成绩。考试结束后,各个考点的成绩将即刻汇总成一张总的排名表。

现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。

输入格式:

输入的第一行给出一个正整数N(≤100),代表考点总数。随后给出N个考点的成绩,格式为:首先一行给出正整数K(≤300),代表该考点的考生总数;随后K行,每行给出1个考生的信息,包括考号(由13位整数字组成)和得分(为[0,100]区间内的整数),中间用空格分隔。

输出格式:

首先在第一行里输出考生总数。随后输出汇总的排名表,每个考生的信息占一行,顺序为:考号、最终排名、考点编号、在该考点的排名。其中考点按输入给出的顺序从1到N编号。考生的输出须按最终排名的非递减顺序输出,获得相同分数的考生应有相同名次,并按考号的递增顺序输出。

输入样例:

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

分析:

       整体比较好理解,用结构体快排即可出答案。

       我用结构体快排做题一般是这样想:明确知道排序为这道题的主要思路;有明确的排序依据(如这道题就是按照分数排序);只需直接或间断排完一次

       该题的一些细节地方:
        1、需要设置一个随输入随计数的sum变量,一是因为需要输出总人数,二是可以达到输入一组就排列一组的目的
        2、long long int的变量
        3、a的下标编号
        4、关于考点排名:不需排列,但需求出
        5、关于总体排名,需要排列,需要求出
            这两类排名名次是不能重复的。例:若有两人都是100分,那么他们都是第一,且99分的人是第三,没有第二的人
           这也是为什么cmp没有选择按排名排列而是分数


代码:(出现一个段错误)

#include<bits/stdc++.h>
using namespace std;
//需要排列
//需要知道考点排名和总体排名
struct student
{
    long long int member;//考号儿
    int goal;//分数
    int point;//考点
    int classn;//考点排名
    int overalln;//总体排名
} a[50001];
bool cmp(student a,student b)
{
    if(a.goal!=b.goal)
        return a.goal>b.goal; //分数不相等,按分数降序排列
    return a.member<b.member; //分数相等,按照考号升序排列
}
int main()
{
    int n;
    int m;
    int i;
    int sum=0;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&m);
        for(int j=sum; j<m+sum; j++)
        {
            scanf("%lld%d",&a[j].member,&a[j].goal);
            a[j].point=i;
        }
        sort(a+sum,a+sum+m,cmp);//随输入随排列

        int k=1;

        for(int j=sum; j<sum+m; j++)
        {
               while(a[j].goal==a[j+1].goal)
             {
                 a[j].classn=k;
                 j++;
             }
             a[j].classn=k;
             k=j-sum+2;

        }
        sum+=m;//不要忘
    }//for

    //输出
    printf("%d
",sum);
    sort(a,a+sum,cmp);
    int k=1;
    for(int j=0; j<sum; j++)
    {
        while(a[j].goal==a[j+1].goal)
        {
            a[j].overalln=k;
            j++;
        }
        a[j].overalln=k;
        k=j+2;//多个同分数的人,越过中间的排名
    }
    for(int j=0; j<sum; j++)
        printf("%013lld %d %d %d
",a[j].member,a[j].overalln,a[j].point,a[j].classn);

}
原文地址:https://www.cnblogs.com/elegantcloud/p/13885557.html