PAT Basic 1085. PAT单位排行

1. 题目描述：

每次 PAT 考试结束后，考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。

2. 输入格式：

输入第一行给出一个正整数 N（\(≤10^5\)），即考生人数。随后 N 行，每行按下列格式给出一个考生的信息：

准考证号 得分 学校

其中准考证号是由 6 个字符组成的字符串，其首字母表示考试的级别：B代表乙级，A代表甲级，T代表顶级；得分是 [0, 100] 区间内的整数；学校是由不超过 6 个英文字母组成的单位码（大小写无关）。注意：题目保证每个考生的准考证号是不同的。

3. 输出格式：

首先在一行中输出单位个数。随后按以下格式非降序输出单位的排行榜：

排名 学校 加权总分 考生人数

其中排名是该单位的排名（从 1 开始）；学校是全部按小写字母输出的单位码；加权总分定义为乙级总分/1.5 + 甲级总分 + 顶级总分*1.5的整数部分；考生人数是该属于单位的考生的总人数。

学校首先按加权总分排行。如有并列，则应对应相同的排名，并按考生人数升序输出。如果仍然并列，则按单位码的字典序输出。

4. 输入样例：

10
A57908 85 Au
B57908 54 LanX
A37487 60 au
T28374 67 CMU
T32486 24 hypu
A66734 92 cmu
B76378 71 AU
A47780 45 lanx
A72809 100 pku
A03274 45 hypu

5. 输出样例：

5
1 cmu 192 2
1 au 192 3
3 pku 100 1
4 hypu 81 2
4 lanx 81 2

6. 性能要求：

Code Size Limit
16 KB
Time Limit
800 ms
Memory Limit
64 MB

思路：

定义结构体School存储每个学校的相关信息，一开始想着最极端的情况是每个考生都属于不同的学校，那么学校数最大为考生人数，所以按照考生人数N分配内存，在输入每个考生信息时若存在对应学校则累加相关信息，不存在则新增学校信息，统计完所有考生信息后调用库函数qsort()进行排序并输出即可。

第一次提交时testpoint4，5报Time Limit Exceeded，考虑到之前类似的情况，应该是输入每个考生信息时遍历判断对应学校是否存在造成的，就改为每次都先按照学校名字排序后二分搜索对应学校是否存在，但仍然超时。。。

无奈上网搜索，找到大佬题解：PAT Basic 1085. PAT单位排行 (C语言实现) - 简书 (jianshu.com) ，额外定义结构体Student存储每位考生的信息，并按照学校名对考生信息进行排序，然后通过类似PAT Basic 1078. 字符串压缩与解压 压缩字符串的逻辑汇总每个学校的信息，最后再按照题意进行排序和输出即可。

My Code:

// #include <stdio.h>
// #include <stdlib.h> // calloc header, qsort header
// #include <ctype.h> // tolower header
// #include <string.h> // strcmp header, strcpy header

// typedef struct school
// {
//     char name[7];
//     int gradeJia;
//     int gradeYi;
//     int gradeDing;
//     int gradeSum;
//     int stuCount;
//     int order;
// } School;

// void str2lower(char *name);
// int myCmp(const void *p1, const void *p2);

// // first submit testpoint4, 5 Time Limit Exceeded
// int main(void)
// {
//     int stuCount = 0;
//     School *pSch = NULL;
//     int i=0, j=0; // iterator
//     int schoolCount = 0;
//     char tempId[7];
//     int tempGrade;
//     char tempSchool[7];
    
//     scanf("%d", &stuCount);
//     pSch = (School *)calloc(stuCount, sizeof(School));
    
//     for(i=0; i<stuCount; ++i)
//     {
//         scanf("%s%d%s", tempId, &tempGrade, tempSchool);
//         str2lower(tempSchool); // lower the tempSchool
        
//         for(j=0; j<schoolCount; ++j) // search in school list
//         {
//             if(!strcmp(pSch[j].name, tempSchool)) // have this school
//             {
//                 ++pSch[j].stuCount;
//                 switch(tempId[0])
//                 {
//                     case 'B':
//                         pSch[j].gradeYi += tempGrade;
//                         break;
//                     case 'A':
//                         pSch[j].gradeJia += tempGrade;
//                         break;
//                     case 'T':
//                         pSch[j].gradeDing += tempGrade;
//                         break;
//                     default:
//                         break;
//                 }
//                 break;
//             }
//         }
//         if(j==schoolCount) // dosen't have this school
//         {
//             strcpy(pSch[schoolCount].name, tempSchool);
//             ++pSch[schoolCount].stuCount;
//             switch(tempId[0])
//             {
//                 case 'B':
//                     pSch[schoolCount].gradeYi += tempGrade;
//                     break;
//                 case 'A':
//                     pSch[schoolCount].gradeJia += tempGrade;
//                     break;
//                 case 'T':
//                     pSch[schoolCount].gradeDing += tempGrade;
//                     break;
//                 default:
//                     break;
//             }
//             ++schoolCount;
//         }
//     }
    
//     for(i=0; i<schoolCount; ++i) // calculate gradeSum
//     {
//         pSch[i].gradeSum = pSch[i].gradeYi/1.5 + pSch[i].gradeJia + pSch[i].gradeDing*1.5;
//         //printf("%s %d %d\n", pSch[i].name, pSch[i].gradeSum, pSch[i].stuCount);
//     }
    
//     qsort(pSch, schoolCount, sizeof(School), myCmp); // sort the school
    
//     printf("%d\n", schoolCount);
    
//     for(i=0; i<schoolCount; ++i)
//     {
//         pSch[i].order = i+1;
//         if(i>0 && pSch[i].gradeSum == pSch[i-1].gradeSum)
//         {
//             pSch[i].order = pSch[i-1].order;
//         }
//         printf("%d %s %d %d\n", pSch[i].order, pSch[i].name, pSch[i].gradeSum, pSch[i].stuCount);
//     }
    
//     free(pSch);
//     return 0;
// }

// void str2lower(char *name)
// {
//     int i=0; // iterator
//     while(name[i]) // traverse name
//     {
//         name[i] = tolower(name[i]);
//         ++i;
//     }
// }

// int myCmp(const void *p1, const void *p2)
// {
//     School *pLeft = (School *)p1;
//     School *pRight = (School *)p2;
    
//     if(pLeft->gradeSum != pRight->gradeSum)
//     {
//         return pRight->gradeSum - pLeft->gradeSum;
//     }
//     else // gradeSum is equal
//     {
//         if(pLeft->stuCount != pRight->stuCount)
//         {
//             return pLeft->stuCount - pRight->stuCount;
//         }
//         else // stuCount also euqal
//         {
//             return strcmp(pLeft->name, pRight->name);
//         }
//     }
    
// }



// #include <stdio.h>
// #include <stdlib.h> // calloc header, qsort header, bsearch header
// #include <ctype.h> // tolower header
// #include <string.h> // strcmp header, strcpy header

// typedef struct school
// {
//     char name[7];
//     int gradeJia;
//     int gradeYi;
//     int gradeDing;
//     int gradeSum;
//     int stuCount;
//     int order;
// } School;

// void str2lower(char *name);
// int myCmp(const void *p1, const void *p2);
// int sort_name(const void *p1, const void *p2);
// int cmp_search(const void *p1, const void *p2);

// // testpoint4, 5 still Time Limit Exceeded
// int main(void)
// {
//     int stuCount = 0;
//     School *pSch = NULL;
//     int i=0; // iterator
//     int schoolCount = 0;
//     char tempId[7];
//     int tempGrade;
//     char tempSchool[7];
//     School *pSearch = NULL;
    
//     scanf("%d", &stuCount);
//     pSch = (School *)calloc(stuCount, sizeof(School));
    
//     for(i=0; i<stuCount; ++i)
//     {
//         scanf("%s%d%s", tempId, &tempGrade, tempSchool);
//         str2lower(tempSchool); // lower the tempSchool
        
//         qsort(pSch, schoolCount, sizeof(School), sort_name); // sort by name for binary search
        
//         pSearch = (School *)bsearch(tempSchool, pSch, schoolCount, sizeof(School), cmp_search); // search in school list
//         if(pSearch) // have this school
//         {
//             ++pSearch->stuCount;
//             switch(tempId[0])
//             {
//                 case 'B':
//                     pSearch->gradeYi += tempGrade;
//                     break;
//                 case 'A':
//                     pSearch->gradeJia += tempGrade;
//                     break;
//                 case 'T':
//                     pSearch->gradeDing += tempGrade;
//                     break;
//                 default:
//                     break;
//             }
//         }
//         else // dosen't have this school
//         {
//             strcpy(pSch[schoolCount].name, tempSchool);
//             ++pSch[schoolCount].stuCount;
//             switch(tempId[0])
//             {
//                 case 'B':
//                     pSch[schoolCount].gradeYi += tempGrade;
//                     break;
//                 case 'A':
//                     pSch[schoolCount].gradeJia += tempGrade;
//                     break;
//                 case 'T':
//                     pSch[schoolCount].gradeDing += tempGrade;
//                     break;
//                 default:
//                     break;
//             }
//             ++schoolCount;
//         }
//     }
    
//     for(i=0; i<schoolCount; ++i) // calculate gradeSum
//     {
//         pSch[i].gradeSum = pSch[i].gradeYi/1.5 + pSch[i].gradeJia + pSch[i].gradeDing*1.5;
//         //printf("%s %d %d\n", pSch[i].name, pSch[i].gradeSum, pSch[i].stuCount);
//     }
    
//     qsort(pSch, schoolCount, sizeof(School), myCmp); // sort the school
    
//     printf("%d\n", schoolCount);
    
//     for(i=0; i<schoolCount; ++i)
//     {
//         pSch[i].order = i+1;
//         if(i>0 && pSch[i].gradeSum == pSch[i-1].gradeSum)
//         {
//             pSch[i].order = pSch[i-1].order;
//         }
//         printf("%d %s %d %d\n", pSch[i].order, pSch[i].name, pSch[i].gradeSum, pSch[i].stuCount);
//     }
    
//     free(pSch);
//     return 0;
// }

// void str2lower(char *name)
// {
//     int i=0; // iterator
//     while(name[i]) // traverse name
//     {
//         name[i] = tolower(name[i]);
//         ++i;
//     }
// }

// int myCmp(const void *p1, const void *p2)
// {
//     School *pLeft = (School *)p1;
//     School *pRight = (School *)p2;
    
//     if(pLeft->gradeSum != pRight->gradeSum)
//     {
//         return pRight->gradeSum - pLeft->gradeSum;
//     }
//     else // gradeSum is equal
//     {
//         if(pLeft->stuCount != pRight->stuCount)
//         {
//             return pLeft->stuCount - pRight->stuCount;
//         }
//         else // stuCount also euqal
//         {
//             return strcmp(pLeft->name, pRight->name);
//         }
//     }
    
// }

// int sort_name(const void *p1, const void *p2)
// {
//     School *pLeft = (School *)p1;
//     School *pRight = (School *)p2;
    
//     return strcmp(pLeft->name, pRight->name);
// }

// int cmp_search(const void *p1, const void *p2)
// {
//     char *name = (char *)p1;
//     School *pSch = (School *)p2;
    
//     return strcmp(name, pSch->name);
// }




#include <stdio.h>
#include <stdlib.h> // calloc header, qsort header, bsearch header
#include <ctype.h> // tolower header
#include <string.h> // strcmp header, strcpy header

typedef struct school
{
    char name[7];
    int grade;
    int stuCount;
    int order;
} School;

typedef struct student
{
    char id[7];
    int grade;
    char school[7];
} Student;

void str2lower(char *name);
int sortBySchool(const void *p1, const void *p2);
int myCmp(const void *p1, const void *p2);

int main(void)
{
    int stuCount = 0;
    School *pSch = NULL;
    int i=0; // iterator
    Student *pStu = NULL;
    int schoolCount = 0;
    double tempGrade = 0.0;
    int tempCount = 0;
    
    scanf("%d", &stuCount);
    pSch = (School *)calloc(stuCount, sizeof(School));
    pStu = (Student *)calloc(stuCount, sizeof(Student));
    
    for(i=0; i<stuCount; ++i)
    {
        scanf("%s%d%s", pStu[i].id, &pStu[i].grade, pStu[i].school);
        str2lower(pStu[i].school);
    }
    
    qsort(pStu, stuCount, sizeof(Student), sortBySchool); // sort by school
    
//     for(i=0; i<stuCount; ++i) // test the sort result
//     {
//         printf("%s %s %d\n", pStu[i].school, pStu[i].id, pStu[i].grade);
//     }
    
    switch(pStu[0].id[0])
    {
        case 'B': tempGrade += pStu[0].grade/1.5;   break;
        case 'A': tempGrade += pStu[0].grade;       break;
        case 'T': tempGrade += pStu[0].grade*1.5;   break;
    }
    tempCount = 1;
    for(i=1; i<stuCount; ++i)
    {
        if(!strcmp(pStu[i].school, pStu[i-1].school)) // have continous same school
        {
            switch(pStu[i].id[0])
            {
                case 'B': tempGrade += pStu[i].grade/1.5;   break;
                case 'A': tempGrade += pStu[i].grade;       break;
                case 'T': tempGrade += pStu[i].grade*1.5;   break;
            }
            ++tempCount;
        }
        else // need to output previous data
        {
            strcpy(pSch[schoolCount].name, pStu[i-1].school);
            pSch[schoolCount].grade = tempGrade;
            pSch[schoolCount].stuCount = tempCount;
            ++schoolCount;
            
            switch(pStu[i].id[0])
            {
                case 'B': tempGrade = pStu[i].grade/1.5;   break;
                case 'A': tempGrade = pStu[i].grade;       break;
                case 'T': tempGrade = pStu[i].grade*1.5;   break;
            }
            tempCount = 1;
        }
    }
    
    // tail handle
    strcpy(pSch[schoolCount].name, pStu[i-1].school);
    pSch[schoolCount].grade = tempGrade;
    pSch[schoolCount].stuCount = tempCount;
    ++schoolCount;
    
    qsort(pSch, schoolCount, sizeof(School), myCmp);
    
    printf("%d\n", schoolCount);
    
    for(i=0; i<schoolCount; ++i)
    {
        pSch[i].order = i+1;
        if(i>0 && pSch[i].grade == pSch[i-1].grade)
        {
            pSch[i].order = pSch[i-1].order;
        }
        printf("%d %s %d %d\n", pSch[i].order, pSch[i].name, pSch[i].grade, pSch[i].stuCount);
    }
    
    free(pSch);
    free(pStu);
    return 0;
}

void str2lower(char *name)
{
    int i=0; // iterator
    while(name[i]) // traverse name
    {
        name[i] = tolower(name[i]);
        ++i;
    }
}

int sortBySchool(const void *p1, const void *p2)
{
    Student *pLeft = (Student *)p1;
    Student *pRight = (Student *)p2;
    
    return strcmp(pLeft->school, pRight->school);
}

int myCmp(const void *p1, const void *p2)
{
    School *pLeft = (School *)p1;
    School *pRight = (School *)p2;
    
    if(pLeft->grade != pRight->grade)
    {
        return pRight->grade - pLeft->grade;
    }
    else if(pLeft->stuCount != pRight->stuCount)
    {
        return pLeft->stuCount - pRight-> stuCount;
    }
    else
    {
        return strcmp(pLeft->name, pRight->name);
    }
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• 陕西高院--总包单位以不欠付款项为由主张不应承担农民工工资清偿责任于法无据
• 微信小程序 wxss——rpx单位
• P1085题解
• Visual Basic 6的安装与辅助插件 - 初学者系列 - 学习者系列文章
• 教育局与学校是一个单位吗？
• 浅谈RS485的单位负载
• 内存访问并非以字节为单位
• 关于对物料计量单位的维护
• 02.SpringBoot3+JDK17+Shiro+Basic认证方式

PAT 单位 Basic 1085pat单位basic 1085 sequence perfect pat_a 1085 单位pat pat-basic pat-basic pat basic 1040 pat-basic basic 1036 pat basic 1046 pat basic 1109 pat pat-basic basic 1039 pat basic 1045 pat