首页 > 其他分享 >PAT Basic 1085. PAT单位排行

PAT Basic 1085. PAT单位排行

时间：2023-04-11 19:55:22浏览次数：60  
标签：1085 PAT name int void School pSch Basic stuCount

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);
    }
}

标签：1085,PAT,name,int,void,School,pSch,Basic,stuCount
From： https://www.cnblogs.com/tacticKing/p/17307446.html

相关文章

  • chromium 的 diff, patcher
    1，编译出来：autoninja-Cout\Defaultcourgette2，使用e:\\chromium\src\out\Default>courgette64.exeFirstargumentmustbeoneof: -supported,-asm,-dis,-disadj,-gen,-apply,-genbsdiff,-applybsdiff,or-gen1[au].MainUsage: courgette-gen<......
  • ida patch
    安装keypatch在GitHub安装下载Keypatch.py复制到插件目录IDA7.0\plugins\Keypatch.py下载安装keystonepython模块，通过pipinstallkeystone-engine或者，64位系统只需要安装https://github.com/keystone-engine/keystone/releases/download/0.9.1/keystone-0.9.1-python-w......
  • Active Directory Basic
    ActiveDirectory是Windows域网络的目录服务介绍ActiveDirectory是在域内部连接的机器和服务器的集合，它们是构成ActiveDirectory网络的更大域林的集合部分。ActiveDirectory包含许多功能部件，ActiveDirectory的各个部分域控制器森林、树木、领域用户+组信托政......
  • (KMP 1.1)hdu 1711 Number Sequence(KMP的简单应用——求pattern在text中第一次出现的
    题目：NumberSequenceTimeLimit:10000/5000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):12902    AcceptedSubmission(s):5845ProblemDescriptionGiventwosequencesofnumbers:a[1],a[2],......,a[N],andb[1......
  • PAT Basic 1082. 射击比赛
    PATBasic1082.射击比赛1.题目描述：本题目给出的射击比赛的规则非常简单，谁打的弹洞距离靶心最近，谁就是冠军；谁差得最远，谁就是菜鸟。本题给出一系列弹洞的平面坐标(x,y)，请你编写程序找出冠军和菜鸟。我们假设靶心在原点(0,0)。2.输入格式：输入在第一行中给出一个正整数N（≤10......
  • Springboot报错：Could not resolve view with name 'index' in servlet with name 'dis
    该异常是因为用定义了带@EnableWebMvc注解的配置类后发生的，在带该注解的配置类中加入下面的代码就可以了：@BeanpublicInternalResourceViewResolverviewResolver(){InternalResourceViewResolverviewResolver=newInternalResourceViewResolver();viewResolver.......
  • PAT Basic 1081. 检查密码
    PATBasic1081.检查密码1.题目描述：本题要求你帮助某网站的用户注册模块写一个密码合法性检查的小功能。该网站要求用户设置的密码必须由不少于6个字符组成，并且只能有英文字母、数字和小数点 .，还必须既有字母也有数字。2.输入格式：输入第一行给出一个正整数N（≤100），随后N......
  • 高性能 Jsonpath 框架，Snack3 3.2.65 发布
    高性能Jsonpath框架，Snack33.2.65发布来源:投稿作者: 梅子酒好吃2023-04-1014:18:00 0Snack3，一个高性能的JsonPath框架借鉴了Javascript所有变量由var申明，及Xmldom一切都是Node的设计。其下一切数据都以ONode表示，ONode也即Onenode之意，代......
  • @RequestParam和@PathVariable的用法与区别
    **@PathVariable**格式@RequestMapping(value="/user/{username}")publicStringuserProfile(@PathVariable(value="username")Stringusername){ return"user"+username;}在上面的例子中，当@Controller处理HTTP请求时，userProfile的参数......
  • PAT Basic 1080. MOOC期终成绩
    PATBasic1080.MOOC期终成绩1.题目描述：对于在中国大学MOOC（http://www.icourse163.org/）学习“数据结构”课程的学生，想要获得一张合格证书，必须首先获得不少于200分的在线编程作业分，然后总评获得不少于60分（满分100）。总评成绩的计算公式为\(G=(G_{mid−term}×40\%+G_{final}×......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99