首页 > 其他分享 >PAT Basic 1095. 解码PAT准考证

PAT Basic 1095. 解码PAT准考证

时间：2023-04-14 15:47:02浏览次数：47  
标签：1095 const int void pLeft pRight Student Basic PAT

PAT Basic 1095. 解码PAT准考证

1. 题目描述：

PAT 准考证号由 4 部分组成：

  • 第 1 位是级别，即 T 代表顶级；A 代表甲级；B 代表乙级；
  • 第 2~4 位是考场编号，范围从 101 到 999；
  • 第 5~10 位是考试日期，格式为年、月、日顺次各占 2 位；
  • 最后 11~13 位是考生编号，范围从 000 到 999。

现给定一系列考生的准考证号和他们的成绩，请你按照要求输出各种统计信息。

2. 输入格式：

输入首先在一行中给出两个正整数 \(N\)（\(≤10^4\)）和 \(M\)（\(≤100\)），分别为考生人数和统计要求的个数。

接下来 \(N\) 行，每行给出一个考生的准考证号和其分数（在区间 \([0,100]\) 内的整数），其间以空格分隔。

考生信息之后，再给出 \(M\) 行，每行给出一个统计要求，格式为：类型 指令，其中

  • 类型 为 1 表示要求按分数非升序输出某个指定级别的考生的成绩，对应的 指令 则给出代表指定级别的字母；
  • 类型 为 2 表示要求将某指定考场的考生人数和总分统计输出，对应的 指令 则给出指定考场的编号；
  • 类型 为 3 表示要求将某指定日期的考生人数分考场统计输出，对应的 指令 则给出指定日期，格式与准考证上日期相同。

3. 输出格式：

对每项统计要求，首先在一行中输出 Case #: 要求，其中 # 是该项要求的编号，从 1 开始；要求 即复制输入给出的要求。随后输出相应的统计结果：

  • 类型 为 1 的指令，输出格式与输入的考生信息格式相同，即 准考证号 成绩。对于分数并列的考生，按其准考证号的字典序递增输出（题目保证无重复准考证号）；
  • 类型 为 2 的指令，按 人数 总分 的格式输出；
  • 类型 为 3 的指令，输出按人数非递增顺序，格式为 考场编号 总人数。若人数并列则按考场编号递增顺序输出。

如果查询结果为空，则输出 NA。

4. 输入样例：

8 4
B123180908127 99
B102180908003 86
A112180318002 98
T107150310127 62
A107180908108 100
T123180908010 78
B112160918035 88
A107180908021 98
1 A
2 107
3 180908
2 999

5. 输出样例：

Case 1: 1 A
A107180908108 100
A107180908021 98
A112180318002 98
Case 2: 2 107
3 260
Case 3: 3 180908
107 2
123 2
102 1
Case 4: 2 999
NA

6. 性能要求：

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

思路：

考察基础IO，定义结构体Student存储考生信息，根据题意分别编写处理三种指令的代码即可。这里我定义子函数handleDirect()处理指令，指令1和指令2的处理比较常规，主要说下我处理指令3的思路：首先筛选出符合指定日期的记录，然后根据准考证号对这些记录进行排序，那么理论上相同考场的记录会连在一起，再根据之前压缩字符串的思路PAT Basic 1078. 字符串压缩与解压 对每一考场的人数计数即可，额外定义结构体Dir3存储各个考场的信息，最后根据人数和考场编号对统计出的考场信息进行排序和输出。

第一次提交时testpoint3报Time Limit Exceeded，回想起之前看别人的博客提到最好不要直接拷贝、移动结构体本身，于是将handleDirect()中的逻辑处理部分改为定义结构体指针数组，存储和排序时使用结构体指针而不是结构体本身，改完后testpoint3又报wrong answer。。。排查了好久才发现是因为准考证号是以级别开头，直接排序的话相同考场的记录可能没有连在一起，疏忽了这一点。。。修改排序函数sort_id()后AC。

My Code:

// #include <stdio.h>
// #include <stdlib.h> // malloc header, qsort header
// #include <string.h> // strcmp header, strncpy header, strcpy header

// typedef struct student
// {
//     char id[14];
//     int grade;
// } Student;

// typedef struct dir3
// {
//     char room[4];
//     int count;
// } Dir3;

// void handleDirect(Student *pStu, int stuCount, int dirType, const char *direct);
// int sort_dir1(const void *p1, const void *p2);
// int sort_id(const void *p1, const void *p2);
// int sort_dir3(const void *p1, const void *p2);

// // first submit testpoint3 Time Limit Exceeded
// int main(void)
// {
//     int stuCount=0, directCount=0;
//     Student *pStu = NULL;
//     int i=0; // iterator
//     int dirType=0;
//     char directive[7] = "";
    
//     scanf("%d%d", &stuCount, &directCount);
    
//     pStu = (Student *)malloc(sizeof(Student) * stuCount); // allocate memory
//     for(i=0; i<stuCount; ++i)
//     {
//         scanf("%s%d", pStu[i].id, &pStu[i].grade);
//         //printf("%s %d\n", pStu[i].id, pStu[i].grade); // test input
//     }
    
//     for(i=0; i<directCount; ++i)
//     {
//         scanf("%d%s", &dirType, directive);
//         //printf("%d %s\n", dirType, directive); // test input
//         printf("Case %d: %d %s\n", i+1, dirType, directive);
//         handleDirect(pStu, stuCount, dirType, directive);
//     }
    
    
//     free(pStu); // free heap memory
//     return 0;
// }

// void handleDirect(Student *pStu, int stuCount, int dirType, const char *direct)
// {
//     Student *pRes = NULL;
//     int resCount = 0; // result iterator
//     int i=0; // iterator
//     /* var for directive2 */
//     char examRoom[4] = "";
//     int gradeSum=0;
//     /* var for directive3 */
//     char date[7] = "";
//     Dir3 *pDir3 = NULL;
//     int dir3Count=0, tempCount=0;
//     char lastRoom[4] = "", tempRoom[4] = ""; // this must be initialize, for strncpy doesn't add '\0'
    
//     pRes = (Student *)malloc(sizeof(Student) * stuCount); // allocate heap memory
    
//     switch(dirType)
//     {
//         case 1: // output a class grade in descending order
//             resCount = 0;
//             for(i=0; i<stuCount; ++i)
//             {
//                 if(pStu[i].id[0] == direct[0]) // is this class
//                 {
//                     pRes[resCount++] = pStu[i];
//                 }
//             }
            
//             if(resCount) // have corresponding info
//             {
//                 qsort(pRes, resCount, sizeof(Student), sort_dir1);
//                 for(i=0; i<resCount; ++i)
//                 {
//                     printf("%s %d\n", pRes[i].id, pRes[i].grade);
//                 }
//             }
//             else // no corresponding info
//             {
//                 printf("NA\n");
//             }
            
//             break;
//         case 2: //
//             resCount = 0;
//             gradeSum = 0;
//             for(i=0; i<stuCount; ++i)
//             {
//                 strncpy(examRoom, pStu[i].id+1, 3); // extract examRoom
//                 if(!strcmp(examRoom, direct)) // is this room
//                 {
//                     ++resCount;
//                     gradeSum += pStu[i].grade;
//                 }
//             }
            
//             if(resCount) // have corresponding info
//             {
//                 printf("%d %d\n", resCount, gradeSum);
//             }
//             else // no corresponding info
//             {
//                 printf("NA\n");
//             }
            
//             break;
//         case 3:
//             resCount = 0;
//             for(i=0; i<stuCount; ++i)
//             {
//                 strncpy(date, pStu[i].id+4, 6); // extract date
//                 if(!strcmp(date, direct)) // is this date
//                 {
//                     pRes[resCount++] = pStu[i];
//                 }
//             }
//             //printf("resCount: %d\n", resCount);
            
//             if(resCount) // have corresponding info
//             {
//                 qsort(pRes, resCount, sizeof(Student), sort_id);
                
// //                 for(i=0; i<resCount; ++i)
// //                 {
// //                     printf("%s %d\n", pRes[i].id, pRes[i].grade);
// //                 }
                
//                 pDir3 = (Dir3 *)malloc(sizeof(Dir3) * resCount);
//                 dir3Count = 0;
//                 tempCount = 1;
//                 strncpy(lastRoom, pRes[0].id+1, 3); // extract examRoom
//                 //printf("lastRoom: %s, strlen(lastRoom): %d\n", lastRoom, strlen(lastRoom)); //strncpy need add '\0' manually
                
//                 for(i=1; i<resCount; ++i)
//                 {
//                     strncpy(tempRoom, pRes[i].id+1, 3); // extract examRoom
//                     if(!strcmp(lastRoom, tempRoom)) // have continous same examRoom
//                     {
//                         ++tempCount;
//                     }
//                     else // does'n have continous same examRoom, need to output lastRoom
//                     {
//                         strcpy(pDir3[dir3Count].room, lastRoom);
//                         pDir3[dir3Count].count = tempCount;
//                         ++dir3Count;
//                         tempCount = 1;
//                     }
//                     strcpy(lastRoom, tempRoom); // update lastRoom
//                 }
                
//                 // tail handle
//                 strcpy(pDir3[dir3Count].room, lastRoom);
//                 pDir3[dir3Count].count = tempCount;
//                 ++dir3Count;
                
                
//                 qsort(pDir3, dir3Count, sizeof(Dir3), sort_dir3);
//                 for(i=0; i<dir3Count; ++i)
//                 {
//                     printf("%s %d\n", pDir3[i].room, pDir3[i].count);
//                 }
//             }
//             else // no corresponding info
//             {
//                 printf("NA\n");
//             }
            
//             break;
//         default:
//             break;
//     }
    
    
//     free(pRes); // release heap memory
//     free(pDir3);
//     return;
// }

// int sort_dir1(const void *p1, const void *p2)
// {
//     Student *pLeft = (Student *)p1;
//     Student *pRight = (Student *)p2;
    
//     if(pRight->grade != pLeft->grade)
//     {
//         return (pRight->grade - pLeft->grade);
//     }
//     else // grade is equal
//     {
//         return strcmp(pLeft->id, pRight->id);
//     }
// }

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

// int sort_dir3(const void *p1, const void *p2)
// {
//     Dir3 *pLeft = (Dir3 *)p1;
//     Dir3 *pRight = (Dir3 *)p2;
    
//     if(pLeft->count != pRight->count)
//     {
//         return (pRight->count - pLeft->count);
//     }
//     else // have same count
//     {
//         return strcmp(pLeft->room, pRight->room);
//     }
// }



#include <stdio.h>
#include <stdlib.h> // malloc header, qsort header
#include <string.h> // strcmp header, strncpy header, strcpy header

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

typedef struct dir3
{
    char room[4];
    int count;
} Dir3;

void handleDirect(Student *pStu, int stuCount, int dirType, const char *direct);
int sort_dir1(const void *p1, const void *p2);
int sort_id(const void *p1, const void *p2);
int sort_dir3(const void *p1, const void *p2);

// after rectify, testpoint3 wrong answer
int main(void)
{
    int stuCount=0, directCount=0;
    Student *pStu = NULL;
    int i=0; // iterator
    int dirType=0;
    char directive[7] = "";
    
    scanf("%d%d", &stuCount, &directCount);
    
    pStu = (Student *)malloc(sizeof(Student) * stuCount); // allocate memory
    for(i=0; i<stuCount; ++i)
    {
        scanf("%s%d", pStu[i].id, &pStu[i].grade);
        //printf("%s %d\n", pStu[i].id, pStu[i].grade); // test input
    }
    
    for(i=0; i<directCount; ++i)
    {
        scanf("%d%s", &dirType, directive);
        //printf("%d %s\n", dirType, directive); // test input
        printf("Case %d: %d %s\n", i+1, dirType, directive);
        handleDirect(pStu, stuCount, dirType, directive);
    }
    
    
    free(pStu); // free heap memory
    return 0;
}

void handleDirect(Student *pStu, int stuCount, int dirType, const char *direct)
{
    //Student *pRes = NULL;
    Student **pRes;
    int resCount = 0; // result iterator
    int i=0; // iterator
    /* var for directive2 */
    char examRoom[4] = "";
    int gradeSum=0;
    /* var for directive3 */
    char date[7] = "";
    Dir3 *pDir3 = NULL;
    int dir3Count=0, tempCount=0;
    char lastRoom[4] = "", tempRoom[4] = ""; // this must be initialize, for strncpy doesn't add '\0'
    
    //pRes = (Student *)malloc(sizeof(Student) * stuCount); // allocate heap memory
    pRes = (Student **)malloc(sizeof(Student *) * stuCount); // allocate pointer of struct instead of struct itself
    
    switch(dirType)
    {
        case 1: // output a class grade in descending order
            resCount = 0;
            for(i=0; i<stuCount; ++i)
            {
                if(pStu[i].id[0] == direct[0]) // is this class
                {
                    pRes[resCount++] = &pStu[i];
                }
            }
            
            if(resCount) // have corresponding info
            {
                qsort(pRes, resCount, sizeof(Student *), sort_dir1);
                for(i=0; i<resCount; ++i)
                {
                    printf("%s %d\n", pRes[i]->id, pRes[i]->grade);
                }
            }
            else // no corresponding info
            {
                printf("NA\n");
            }
            
            break;
        case 2: //
            resCount = 0;
            gradeSum = 0;
            for(i=0; i<stuCount; ++i)
            {
                strncpy(examRoom, pStu[i].id+1, 3); // extract examRoom
                if(!strcmp(examRoom, direct)) // is this room
                {
                    ++resCount;
                    gradeSum += pStu[i].grade;
                }
            }
            
            if(resCount) // have corresponding info
            {
                printf("%d %d\n", resCount, gradeSum);
            }
            else // no corresponding info
            {
                printf("NA\n");
            }
            
            break;
        case 3:
            resCount = 0;
            for(i=0; i<stuCount; ++i)
            {
                strncpy(date, pStu[i].id+4, 6); // extract date
                if(!strcmp(date, direct)) // is this date
                {
                    pRes[resCount++] = &pStu[i];
                }
            }
            //printf("resCount: %d\n", resCount);
            
            if(resCount) // have corresponding info
            {
                qsort(pRes, resCount, sizeof(Student *), sort_id);
                
//                 for(i=0; i<resCount; ++i)
//                 {
//                     printf("%s %d\n", pRes[i]->id, pRes[i]->grade);
//                 }
                
                pDir3 = (Dir3 *)malloc(sizeof(Dir3) * resCount);
                dir3Count = 0;
                tempCount = 1;
                strncpy(lastRoom, pRes[0]->id+1, 3); // extract examRoom
                lastRoom[3] = 0;
                //printf("lastRoom: %s, strlen(lastRoom): %d\n", lastRoom, strlen(lastRoom)); //strncpy need add '\0' manually
                
                for(i=1; i<resCount; ++i)
                {
                    strncpy(tempRoom, pRes[i]->id+1, 3); // extract examRoom
                    tempRoom[3] = 0;
                    if(!strcmp(lastRoom, tempRoom)) // have continous same examRoom
                    {
                        ++tempCount;
                    }
                    else // does'n have continous same examRoom, need to output lastRoom
                    {
                        strcpy(pDir3[dir3Count].room, lastRoom);
                        pDir3[dir3Count].count = tempCount;
                        ++dir3Count;
                        tempCount = 1;
                    }
                    strcpy(lastRoom, tempRoom); // update lastRoom
                }
                
                // tail handle
                strcpy(pDir3[dir3Count].room, lastRoom);
                pDir3[dir3Count].count = tempCount;
                ++dir3Count;
                
                
                qsort(pDir3, dir3Count, sizeof(Dir3), sort_dir3);
                for(i=0; i<dir3Count; ++i)
                {
                    printf("%s %d\n", pDir3[i].room, pDir3[i].count);
                }
            }
            else // no corresponding info
            {
                printf("NA\n");
            }
            
            break;
        default:
            break;
    }
    
    
    free(pRes); // release heap memory
    free(pDir3);
    return;
}

int sort_dir1(const void *p1, const void *p2)
{
    Student *pLeft = *(Student **)p1;
    Student *pRight = *(Student **)p2;
    
    if(pRight->grade != pLeft->grade)
    {
        return (pRight->grade - pLeft->grade);
    }
    else // grade is equal
    {
        return strcmp(pLeft->id, pRight->id);
    }
}

int sort_id(const void *p1, const void *p2)
{
    Student *pLeft = *(Student **)p1;
    Student *pRight = *(Student **)p2;
    
    return strcmp(pLeft->id+1, pRight->id+1); // here fixed testpoint3
}

int sort_dir3(const void *p1, const void *p2)
{
    Dir3 *pLeft = (Dir3 *)p1;
    Dir3 *pRight = (Dir3 *)p2;
    
    if(pLeft->count != pRight->count)
    {
        return (pRight->count - pLeft->count);
    }
    else // have same count
    {
        return strcmp(pLeft->room, pRight->room);
    }
}

标签：1095,const,int,void,pLeft,pRight,Student,Basic,PAT
From： https://www.cnblogs.com/tacticKing/p/17318490.html

相关文章

  • re.findall()用法详解-返回string中所有与pattern相匹配的全部字串
    re.findall()：函数返回包含所有匹配项的列表。返回string中所有与pattern相匹配的全部字串，返回形式为数组。  示例代码1：【打印所有的匹配项】   importre       s="Longlivethepeople'sRepublicofChina"   ret=re.findall('h',s)       ......
  • 3.2 Go语言从入门到精通：包管理工具之GOPATH
    当我们真正用Go去做项目，或者阅读Go项目（如，Go实现的开源项目）时，不可避免的会遇到包依赖问题，一些包管理方式总是很难区分、选择。Go的包管理与Java的Maven依赖管理不太一样，起初Go的包管理方式经常会被人吐槽，但随之Go版本的升级也出现了不同的包管理方式，以满足不同的需求。今天，我们......
  • Navicat常见错误怎么处理（Rsa Public Key not Find、Generate First a serial、No All
    一：下载一键提取软件提取码:rtce1.Navicat数据库管理工具：NavicatDBeaver数据库管理工具：可以代替Navicat2.NavicatKeygenPatch：激活工具二：安装激活1.安装Navicat：直接下一步即可安装NavicatKeygenPatch：安装好后即可打开使用2.断网、关闭杀毒软件和本地防火墙3.......
  • Node.js文件路径：Path模块
    path模块是nodejs的内置模块，便于我们去获取、操作文件路径记录一些注意事项：文件的绝对位置cjsconsole.log(__filename)mjsmjs中，不能使用__filename和__dirnameconsole.log(import.meta.url)文件所处的目录cjsconsole.log(__dirname)mjsimport{dirname}from"path......
  • Codeforces Round #303 (Div. 2) E. Paths and Trees (最短路+变形最小生成树)
    题目地址：E.PathsandTrees模拟了一场CF，这场实在太水了。。边玩边做的。。最后半分钟交了一发E题。。不幸AK绝杀失败。。。。首先的思路肯定是先求最短路，把可能为最短路的边挑出来，然后第二步我本来写的是直接用无向图的最小生成树，于是绝杀失败。。。后来才发现这样是不行的。......
  • PAT Basic 1094. 谷歌的招聘
    PATBasic1094.谷歌的招聘1.题目描述：2004年7月，谷歌在硅谷的101号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以.com结尾的网址，而前面的网址是一个10位素数，这个素数是自然常数e中最早出现的10位连续数字。能找出这个素数的人，就可以通过访......
  • Visual Stadio 编译提示 The BaseOutputPath/OutputPath property is not set for pr
    完整的错误信息是：TheBaseOutputPath/OutputPathpropertyisnotsetforproject'xx.csproj'.PleasechecktomakesurethatyouhavespecifiedavalidcombinationofConfigurationandPlatformforthisproject.Configuration='Debug'Plat......
  • DispatcherServlet 是一个 Servlet 也是一个bean
    ServletDispatcherServlet实现了javax.servlet.Servlet接口，负责处理来自客户端浏览器的HTTP请求，并将请求分发给相应的Controller进行处理。DispatcherServlet通常是Web应用程序中唯一一个Servlet，并且是SpringMVC框架中最核心的组件之一。SpringBoot启动时会初始化Tomcat容器......
  • PAT Basic 1093. 字符串A+B
    PATBasic1093.字符串A+B1.题目描述：给定两个字符串 \(A\) 和 \(B\)，本题要求你输出 \(A+B\)，即两个字符串的并集。要求先输出 \(A\)，再输出 \(B\)，但重复的字符必须被剔除。2.输入格式：输入在两行中分别给出 \(A\) 和 \(B\)，均为长度不超过 \(10^6\)的、由可见ASCII......
  • PAT Basic 1091. N-自守数
    PATBasic1091.N-自守数1.题目描述：如果某个数\(K\)的平方乘以\(N\)以后，结果的末尾几位数等于\(K\)，那么就称这个数为“\(N\)-自守数”。例如\(3×92^2=25392\)，而\(25392\)的末尾两位正好是\(92\)，所以\(92\)是一个\(3\)-自守数。本题就请你编写程序判断一个给定的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99