PAT乙级 | 1095 解码PAT准考证 (25分)(做题过程+注意事项+运行超时解决方法)

标签: PAT  算法  c++

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

第 1 位是级别,即 T 代表顶级;A 代表甲级;B 代表乙级;
第 2~4 位是考场编号,范围从 101 到 999;
第 5~10 位是考试日期,格式为年、月、日顺次各占 2 位;
最后 11~13 位是考生编号,范围从 000 到 999。
现给定一系列考生的准考证号和他们的成绩,请你按照要求输出各种统计信息。

输入格式:

输入首先在一行中给出两个正整数 N(≤104)和 M(≤100),分别为考生人数和统计要求的个数。

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

考生信息之后,再给出 M 行,每行给出一个统计要求,格式为:类型 指令,其中

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

输出格式:

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

类型 为 1 的指令,输出格式与输入的考生信息格式相同,即 准考证号 成绩。对于分数并列的考生,按其准考证号的字典序递增输出(题目保证无重复准考证号);
类型 为 2 的指令,按 人数 总分 的格式输出;
类型 为 3 的指令,输出按人数非递增顺序,格式为 考场编号 总人数。若人数并列则按考场编号递增顺序输出。
如果查询结果为空,则输出 NA。

输入样例:

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

输出样例:

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

思路:一开始看这题,这不是挺简单的嘛,就是把三个问题合在了一起,后面发现这题并不是想象的那么简单,都最后一个题了,马上脱坑了啊,于是越看越乱,差点饶晕了,这个题就是有点饶,然后也杠了1个晚上,到第二天凌晨1点前,终于杠过去了,ac后参考了下柳婼的代码,大神还是大神,代码行数是我的一半。
第一个要我们按照等级排序,需要注意排序条件
第二个则是要我们输出对应考场的人数和总分,这一个相对其它两个算是最简单的。
第三个是让我们在同一时间里,把参赛的学校按照报考人数排序,博主就饶在这里,饶了很久,想尽办法如何只用一个结构体解决,后面发现不行了,于是又定义了一个结构体用于存放考场编号和人数,并且设置了两个排序条件。
有了这想法后,将各个问题逐个解答,后面提交时测试点3运行超时,过不了,于是又各种魔改代码,尽量减少时间复杂度,cin、cout都换成scanf和printf,后面代码耗时少了,但是测试点3依旧过不去。这个就是代码结构的问题了,当时图书馆要闭馆了,bug不改完又睡不着觉,于是回宿舍继续弄,弄了差不多一个小时终于ac,因为我想到,我们可以在输入学号和分数时就进行处理,把TAB这三个等级分出来,同一天考的也分出来,还有同一个考场也分出来,然后再把该排序的排序,因为如果是在输入指令后进行处理,那么就有可能出现重复处理的情况,耗时自然也就高了。

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

struct student{	//考生
    string number;	//考号
    int score;	//得分
};

struct school{	//考场
    string name;	//考场编号
    int people;	//考场人数
}sch;

bool cmp1(student a,student b){	
    if(a.score!=b.score) return a.score>b.score;
    return a.number<b.number;
}

bool cmp2(school a,school b){
    if(a.people!=b.people) return a.people>b.people;
    return a.name<b.name;
}

int main()
{
    int n,m,k;
    string s;
    char ch[20];	//为了减少复杂度(可以减少15ms左右)
    cin >>n>>m;
    vector<student> v(n);	//存放考生信息
    set<string> st;	//存放考场信息
    map<string,vector<student> > m0,m1,m2;	//分别是1、2、3条件的分类
    for(int i=0;i<n;i++){
        scanf("%s %d",ch,&v[i].score);
        v[i].number=ch;
        string tmp0=v[i].number.substr(0,1);	//分类,第一类
        string tmp1=v[i].number.substr(1,3);	//分类,第二类
        string tmp2=v[i].number.substr(4,6);	//分类,第三类
        m0[tmp0].push_back(v[i]);	//归类
        m1[tmp1].push_back(v[i]);	//归类
        m2[tmp2].push_back(v[i]);	//归类
        st.insert(tmp2);	//将考场插入集合中(因为set可以自动去重)
    }
    sort(m0["A"].begin(),m0["A"].end(),cmp1);	//对TAB进行排序处理
    sort(m0["B"].begin(),m0["B"].end(),cmp1);
    sort(m0["T"].begin(),m0["T"].end(),cmp1);
    map<string,vector<school> > mp;	
    for(set<string>::iterator it=st.begin();it!=st.end();it++){	//每个日期里都有不同的考生
        map<string,int> m_tmp;	//用于获取某考场的索引
        int len=1;
		for(int j=0;j<m2[*it].size();j++){
			s=m2[*it][j].number.substr(1,3);
            if(m_tmp[s]==0){	//如果该考场还未出现过
                sch.name=s;
                sch.people=0;
                mp[*it].push_back(sch);
                m_tmp[s]=len++;
            }
            mp[*it][m_tmp[s]-1].people++;
        }
        sort(mp[*it].begin(),mp[*it].end(),cmp2);	//将该天考场排序
    }
    for(int i=0;i<m;i++){
        scanf("%d",&k);
        cin >>s;
        int flag=0;
        printf("Case %d: %d %s\n",i+1,k,s.c_str());
        if(k==1){	//第一类
            for(int j=0;j<m0[s].size();j++){
                printf("%s %d\n",m0[s][j].number.c_str(),m0[s][j].score);
                flag=1;
            }
        }
        else if(k==2){	//第二类
            int cnt=0;
            for(int j=0;j<m1[s].size();j++){	
                cnt+=m1[s][j].score;	//统计总分
                flag=1;
            }
            if(flag==1) printf("%d %d\n",m1[s].size(),cnt);
        }
        else if(k==3){	//第三类
            for(int j=0;j<mp[s].size();j++){
                flag=1;
                printf("%s %d\n",mp[s][j].name.c_str(),mp[s][j].people);
            }
        }
        if(!flag) printf("NA\n");	//表示查询不到
    }
    return 0;
}

在这里插入图片描述

版权声明:本文为qq_44888152原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44888152/article/details/108937125

智能推荐

Python学习练习6----列表、字典的运用2

range 用法参见http://blog.csdn.net/chiclewu/article/details/50592368 直接在 在线编程工具中练习: https://www.tutorialspoint.com/execute_python_online.php 代码如下,增加range、列表的len()、字典的items()函数,for 函数也有了新变化 练习2: 2的运行结果,注意p...

PoolThreadCache

缓存构成   PoolThreadCache的缓存由三部分构成:tiny、small 和 normal。 tiny   缓存数据大小区间为[16B, 496B]数据,数组长度为32,根据数据大小计算索引的办法:数据大小除以16,如下代码所示: small   缓存数据大小区间为[512B, 4KB]数据,数组长度为4,根据数据大小计算索引的办法:数据大小除以512,然后log2得到指数,如下代码所...

Intellij IDEA 搭建Spring Boot项目(一)

Intellij IDEA 搭建Spring Boot项目 标签(空格分隔): SpringBoot JAVA后台 第一步 选择File –> New –> Project –>Spring Initialer –> 点击Next  第二步 自己修改 Group 和 Artif...

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

猜你喜欢

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...