美文网首页
(原创PAT乙级1085 PAT单位排行)

(原创PAT乙级1085 PAT单位排行)

作者: 仰天蓬蒿人 | 来源:发表于2019-02-15 12:50 被阅读0次

    题目

    1085 PAT单位排行 （25 分）
    每次 PAT 考试结束后，考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。
    输入格式：
    输入第一行给出一个正整数 N（≤10的5次方），即考生人数。随后 N 行，每行按下列格式给出一个考生的信息：
    准考证号 得分 学校
    其中准考证号是由 6 个字符组成的字符串，其首字母表示考试的级别：B代表乙级，A代表甲级，T代表顶级；得分是 [0, 100] 区间内的整数；学校是由不超过 6 个英文字母组成的单位码（大小写无关）。注意：题目保证每个考生的准考证号是不同的。
    输出格式：
    首先在一行中输出单位个数。随后按以下格式非降序输出单位的排行榜：
    排名 学校 加权总分 考生人数
    其中排名是该单位的排名（从 1 开始）；学校是全部按小写字母输出的单位码；加权总分定义为乙级总分/1.5 + 甲级总分 + 顶级总分*1.5的整数部分；考生人数是该属于单位的考生的总人数。
    学校首先按加权总分排行。如有并列，则应对应相同的排名，并按考生人数升序输出。如果仍然并列，则按单位码的字典序输出。

    思考过程

    做题过程中，咋看上去逻辑很简单，做起来却在某个点里想了好久，代码也随之更换了几次版本，这个点就是map的思想，一开始有考虑map，但是不想这么快就用，想想用以往的知识是否可以代替这个功能。

    先说说我的解题逻辑：

    根据题目要求，建立学校结构体，包含着学校名字，各考试类型分数，还有总分和该校的考试人数，并建立该结构体数组。
    1.每录入一个学生的考试类型，成绩和学校名字，然后根据其考试类型，计入该学生所属学校的总分。
    2.上面录完全部学生信息，这时学校的总分和考试人数信息也搞完了，接着就是排序，按照题目的要求来排序，这里我试过了两种排序，一个stl的sort，另一种是自己写的堆排序，结果是前者略快一点，唉
    3.输出

    这里唯一令我尝试了多种方法的是怎么让录入已经重复学校的信息能尽快找出来对应的，其实就是map功能。
    主要分成三次尝试

    第一次尝试，计算学校名字字符串的hash值，自定义的，二十六进制，6位，理论上程序是走得通，或者小量数据也可，但是乘法原理就是加法，十万个数据，数组空间达到了3E以上，每算一个学生的学校名字时候一直用乘法计算它的hash值，在最后测试点内存超限了，果然不行。
    第二次尝试，我尝试再第一次的基础上改进，减少乘法，并且减少空间，采用之前学过的链地址法+3位二十六进制+对比后三位字符串，每发现新的就重新开辟一个，理论上程序也是走得通，或者小量数据也可，但是测试点就是这么神奇，你开辟空间太多次了，倒数第二个测试点就运行超时，估计这个测试点，让我的hash重复率高导致开辟次数达到上万次，这的确耗时，比较伤心，当然你可以把全空间预先全部覆盖好，弄成二维数组，第一维的维数会高达上万，空间浪费太大，加上链地址法上查找也会按照O(n)时间复杂度查找，已经达不到map的功能。然后我又想尝试投石问路，把二十六进制推进到4位又或者3位26进制+后三位的ASCII值，但觉得此时在此题浪费时间过多了，不想继续了，日后再想想。
    第三次尝试，基于这个查找的特点，我只需要查重而已，直接启用C++的unordered_map，来代替自定义计算hash值，其余逻辑没变，通过...

    unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）
    优点： 因为内部实现了哈希表，因此其查找速度非常的快
    缺点： 哈希表的建立比较耗费时间

    一刷代码

    image.png 
    #include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <stdlib.h>
#define MAX_LENGTH 26 * 26 * 26 * 26 * 26 * 26 + 6 

/*
1085 PAT单位排行 （25 分）

*/
using namespace std;
typedef struct School
{
    int id; //学校字符串的hash值 
    char name[7];
    int cScore;//乙级 
    int bScore;//甲级 
    int aScore;//顶级 
    int scores;
    int personCount;
}School;


typedef struct HashMap
{
    unsigned int hashTableKey, hashTableValue;
}HashMap;


int GetIntputToInt();
void GetInputToChar(char ch[]);
bool cmp(School a, School b);
int hashFunc(char S[]);
//void HeapSort(School target[],int n);
//void Sift(School target[],int low,int high);
//void SwapSchool(School target[],int a,int b);

//HashMap map[MAX_LENGTH];

int main()
{
    HashMap *map = (HashMap*)malloc(sizeof(HashMap)*MAX_LENGTH);
    int N = GetIntputToInt();//考生总数 
    School *school = (School*)malloc(sizeof(School)*N);//考虑最坏情况，每个学生就代表一个不同的学校 

    //1.输入每个学生的情况 
    char stuNoTemp[7], nameTemp[7];
    int tempScore, schoolNum = 0;
    char c;
    for (int i = 0; i<N; i++)
    {//i负责遍历学生，j负责学校个数 
        //1.获取编号
        GetInputToChar(stuNoTemp);
        c = stuNoTemp[0];//取出其考试类型 
        //2.获取成绩
        tempScore = GetIntputToInt();
        //3.获取学校名字
        GetInputToChar(nameTemp);
        int id = hashFunc(nameTemp);
        int tempSchoolPos = schoolNum;
        if (map[id].hashTableKey)
        {//id存在的话，要向前找 
            //          while (school[--tempSchoolPos].id != id&&tempSchoolPos >= 0)//超时原因 
            //              ;
            tempSchoolPos = map[id].hashTableValue;
        }
        else
        {//不存在的话
            map[id].hashTableKey = 1;
            map[id].hashTableValue = tempSchoolPos;
            school[tempSchoolPos].id = id;
            strcpy(school[tempSchoolPos].name, nameTemp);
            schoolNum++;//学校数量增1 
        }

        //根据考试类型增加其对应考试类型的总分 
        switch (c)
        {
        case 'a':school[tempSchoolPos].bScore += tempScore;//a是advanced，对应bscore 
            break;
        case 'b':school[tempSchoolPos].cScore += tempScore;//b是basic，对应cscore 
            break;
        case 't':school[tempSchoolPos].aScore += tempScore;
            break;
        default:break;
        }
        //更新该学校参与考试的人数
        school[tempSchoolPos].personCount++;
    }

    //2.统计学校的总分
    for (int i = 0; i<schoolNum; i++)
        school[i].scores = school[i].cScore / 1.5 + school[i].bScore + school[i].aScore*1.5;

    //3.排序
    sort(school, school + schoolNum, cmp);

    //4.输出
    printf("%d\n", schoolNum);
    for (int i = 0, j = 1; i<schoolNum; i++)
    {
        if (i>0 && school[i].scores != school[i - 1].scores)
            j = i + 1;
        printf("%d %s %d %d\n", j, school[i].name, school[i].scores, school[i].personCount);
    }
    //5.释放
    //free(hashTableKey);
    //free(hashTableValue);
    //hashTableKey = NULL;
    //hashTableValue = NULL;

    return 0;
}

bool cmp(School a, School b)
{
    if (a.scores != b.scores) return a.scores>b.scores;
    else if (a.personCount != b.personCount) return a.personCount<b.personCount;
    else return strcmp(a.name, b.name)<0;
}

void GetInputToChar(char ch[])
{
    int i = 0;
    char c;
    while ((c = getchar()) != EOF&&c != ' '&&c != '\n')
    {
        if (c >= 'A'&&c <= 'Z')
            c = c + 32;
        ch[i++] = c;
    }
    ch[i] = '\0';
}

int GetIntputToInt()
{
    char c;
    int sum = 0;
    while ((c = getchar()) != EOF&&c != ' '&&c != '\n')
        sum = sum * 10 + c - '0';
    return sum;
}

int hashFunc(char S[])
{
    int id = 0, i = 0;
    while (S[i] != '\0')
    {
        id = id * 26 + S[i++] - 'a';
    }
    return id + i;//若然是aaa,a这两个值是相同的，所以把长度也加上。 
}

    二刷代码

    image.png 
    #include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <stdlib.h>

/*
1085 PAT单位排行 （25 分）

*/
using namespace std;
typedef struct School
{
    //int id; //学校字符串的hash值 
    char name[7];
    int scores, ascore, bscore, tscore;
    int personCount;
}School;


typedef struct LinkHashNode
{
    int SchoolPos;
    char str[4];
    int viceHash;
    //char str[7];
    struct LinkHashNode *next;
}LinkHashNode;


int GetIntputToInt();//1.输入转成int 
int GetInputToChar(char ch[]);//2.输入转成字符串 
bool cmp(School a, School b);//3.STL中的sort用到的cmp方法 


int GetHashFunc(char S[], int *viceHash);//4.计算字符串中的哈希值
//int GetVicHashFunc(char S[]); 
void InsertStrHash(char S[], int id, int NewSchoolPos, int SViceHash);
int IsSchoolPosExists(char S[], int id, int SViceHash);
//unsigned int hashFunc(char S[],int length);
//void HeapSort(School target[],int n);
//void Sift(School target[],int low,int high);
//void SwapSchool(School target[],int a,int b);

const int MAX_LENGTH = 26 * 26 * 26 + 6 + 26 * 3;//26*26*26*26*26*26+6;//(26+26)*26*26*26*26+6;//
LinkHashNode map[MAX_LENGTH];//={{-1."",NULL}};
int main()
{
    int N = GetIntputToInt();//考生总数 
    School *school = (School*)malloc(sizeof(School)*(N));//考虑最坏情况，每个学生就代表一个不同的学校 

    //初始化 
    for (int i = 0; i<N; i++)
        school[i].personCount = school[i].scores = 0;//school[i].aScore = school[i].bScore = school[i].cScore = 
    for (int i = 0; i<MAX_LENGTH; i++)
        map[i].SchoolPos = -1;

    //1.输入每个学生的情况 
    char stuNoTemp[7], nameTemp[7];
    int tempScore, schoolNum = 0;
    char c;
    for (int i = 0; i<N; i++)
    {//i负责遍历学生个数，schoolNum负责学校个数 
        //1.获取编号
        GetInputToChar(stuNoTemp);
        c = stuNoTemp[0];//取出其考试类型 
        //2.获取成绩
        int tempScore = GetIntputToInt();
        //3.获取学校名字
        GetInputToChar(nameTemp);
        //int id =  hashFunc(nameTemp,nameLength);//超时原因，乘法太多，加法原理
        int viceHash = 0;
        //viceHash=0;
        int id = GetHashFunc(nameTemp, &viceHash);//主部哈希对比 

        int tmpSchoolPos = IsSchoolPosExists(nameTemp, id, viceHash);

        if (tmpSchoolPos<0) //若然找不到School数组位置 
        {
            tmpSchoolPos = schoolNum++;
            InsertStrHash(nameTemp, id, tmpSchoolPos, viceHash);//这个注释了就
            strcpy(school[tmpSchoolPos].name, nameTemp);
            //schoolNum++;//学校数量增1
        }

        //根据考试类型增加其对应考试类型的总分 
        switch (c)
        {
        case 'a':school[tmpSchoolPos].ascore += tempScore;//a是advanced，对应bscore 
            break;
        case 'b':school[tmpSchoolPos].bscore += tempScore;//b是basic，对应cscore 
            break;
        case 't':school[tmpSchoolPos].tscore += tempScore;
            break;
        default:break;
        }
        //更新该学校参与考试的人数
        school[tmpSchoolPos].personCount++;
    }

    //2.统计学校的总分
    for (int i = 0; i<schoolNum; i++)
        school[i].scores = school[i].bscore / 1.5 + school[i].ascore + school[i].tscore*1.5;

    //3.排序
    sort(school, school + schoolNum, cmp);

    //4.输出
    printf("%d\n", schoolNum);
    for (int i = 0, j = 1; i<schoolNum; i++)
    {
        if (i>0 && school[i].scores != school[i - 1].scores)
            j = i + 1;
        printf("%d %s %d %d\n", j, school[i].name, school[i].scores, school[i].personCount);
    }


    //5.释放 
    //  free(map);
    //  free(school);
    //  map = NULL;
    //  school = NULL;

    return 0;
}

bool cmp(School a, School b)
{
    if (a.scores != b.scores) return a.scores>b.scores;
    else if (a.personCount != b.personCount) return a.personCount<b.personCount;
    else return strcmp(a.name, b.name)<0;
}

int GetInputToChar(char ch[])
{
    int i = 0;
    char c;
    while ((c = getchar()) != EOF&&c != ' '&&c != '\n')
    {
        if (c >= 'A'&&c <= 'Z')
            c = c + 32;
        ch[i++] = c;
    }
    ch[i] = '\0';
    return i;
}

int GetIntputToInt()
{
    char c;
    int sum = 0;
    while ((c = getchar()) != EOF&&c != ' '&&c != '\n')
        sum = sum * 10 + c - '0';
    return sum;
}


int GetVicHashFunc(char S[])
{
    int id = 0, i = 3;
    while (S[i] != '\0')
        //id = id * 26+ S[i++] - 'a';//26 
        id += S[i++] - 'a';
    return id + i - 3;//a,aaa也返回0，i-3是其长度避免返回同样的值 
}

int GetHashFunc(char S[], int *vicHash)
{
    int id = 0, i = 0;
    while (S[i] != '\0'&&i<3)
        id = id * 26 + S[i++] - 'a';//26 

    while (S[i] != '\0'&&i >= 3)//字符长度超出3，就另外计算后面的哈希值
        *vicHash = *vicHash + S[i++] - 'a' + 1;//26 

    return id + i;//若然是aaa,a这两个值是相同的，所以把长度也加上。 
}

int IsSchoolPosExists(char S[], int id, int SViceHash)
{
    LinkHashNode *tmpNode = &map[id];
    if (tmpNode->SchoolPos >= 0)
    {
        if (SViceHash>0)
        {
            do
            {
                //if(strcmp(S,tmpNode->str)==0)
                if (tmpNode->viceHash == SViceHash)
                {
                    int i = 3, j = 0;
                    //strcmp(S+3,tmpNode->str)==0
                    while (S[i] != '\0')
                    {
                        if (S[i] != tmpNode->str[j])
                            break;
                        i++; j++;
                    }

                    if (S[i] == '\0'&&tmpNode->str[j] == '\0')
                        return tmpNode->SchoolPos;
                }

                tmpNode = tmpNode->next;
            } while (tmpNode);
        }
        else if (SViceHash == 0)
            return tmpNode->SchoolPos;
    }
    return -1;
}

void InsertStrHash(char S[], int id, int NewSchoolPos, int SViceHash)
{
    LinkHashNode *tmpNode = &map[id];
    int i = 0, j = 0;//i控制S，j控制tmpNode->str 
    if (tmpNode->SchoolPos >= 0)//若然第一个不是空的，向下查空的为止 
    {
        while (tmpNode->next != NULL)
            tmpNode = tmpNode->next;
        LinkHashNode *newNode = (LinkHashNode *)malloc(sizeof(LinkHashNode));
        tmpNode->next = newNode;
        tmpNode = tmpNode->next;
    }

    if (SViceHash>0)
        strcpy(tmpNode->str, S + 3);
    tmpNode->viceHash = SViceHash;//GetHashFunc(S,4);
    tmpNode->SchoolPos = NewSchoolPos;

    tmpNode->next = NULL;
}

    三刷代码

    image.png 
    #include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <stdlib.h>
#include <unordered_map>

/*
1085 PAT单位排行 （25 分）

*/
using namespace std;
typedef struct School
{
    //int id; //学校字符串的hash值 
    //string name;
    char name[7];
    int ascore, bscore, tscore;
    int scores;
    int personCount;
}School;

int GetIntputToInt();//1.输入转成int 
int GetInputToChar(char ch[]);//2.输入转成字符串 
bool cmp(School a, School b);//3.STL中的sort用到的cmp方法 
int main()
{
    int N = GetIntputToInt();//考生总数 
    School *school = (School*)malloc(sizeof(School)*(N + 1));//考虑最坏情况，每个学生就代表一个不同的学校 
    //  
    //1.输入每个学生的情况
    unordered_map<string, int> schoolHash;
    char stuNoTemp[7], nameTemp[7];
    int schoolNum = 0;
    char c;
    for (int i = 0; i<N; i++)
    {//i负责遍历学生个数，schoolNum负责学校个数 

        //1.获取编号
        GetInputToChar(stuNoTemp);
        c = stuNoTemp[0];//取出其考试类型 
        //2.获取成绩
        int tempScore = GetIntputToInt();
        //3.获取学校名字
        GetInputToChar(nameTemp);
        string strSchoolName = nameTemp;//这里strSchoolName只用来unordered_map的比较寻找


        int tmpSchoolPos;
        if (schoolHash.find(strSchoolName) == schoolHash.end())
        {
            schoolHash[strSchoolName] = tmpSchoolPos = schoolNum++;
            strcpy(school[tmpSchoolPos].name, nameTemp);
        }
        else
            tmpSchoolPos = schoolHash[strSchoolName];

        //根据考试类型增加其对应考试类型的总分 
        switch (c)
        {
        case 'a':school[tmpSchoolPos].ascore += tempScore;//a是advanced，对应bscore 
            break;
        case 'b':school[tmpSchoolPos].bscore += tempScore;// / 1.5;//b是basic，对应cscore 
            break;
        case 't':school[tmpSchoolPos].tscore += tempScore;//*1.5;
            break;
        default:break;
        }
        //更新该学校参与考试的人数
        school[tmpSchoolPos].personCount++;
    }

    //2.统计学校的总分
    for (int i = 0; i<schoolNum; i++)
        school[i].scores = school[i].bscore / 1.5 + school[i].ascore + school[i].tscore*1.5;

    //3.排序
    sort(school, school + schoolNum, cmp);

    //4.输出
    printf("%d\n", schoolNum);
    for (int i = 0, j = 1; i <schoolNum; i++)
    {
        if (i>0 && school[i].scores != school[i - 1].scores)
            j = i + 1;
        printf("%d %s %d %d\n", j, school[i].name, school[i].scores, school[i].personCount);
    }


    //5.释放 
    //  free(map);
    //  free(school);
    //  map = NULL;
    //  school = NULL;

    return 0;
}

bool cmp(School a, School b)
{
    if (a.scores != b.scores) return a.scores>b.scores;
    else if (a.personCount != b.personCount) return a.personCount<b.personCount;
    else return strcmp(a.name, b.name)<0;
}

int GetInputToChar(char ch[])
{
    int i = 0;
    char c;
    while ((c = getchar()) != EOF&&c != ' '&&c != '\n')
    {
        if (c >= 'A'&&c <= 'Z')
            c = c + 32;
        ch[i++] = c;
    }
    ch[i] = '\0';
    return i;
}

int GetIntputToInt()
{
    char c;
    int sum = 0;
    while ((c = getchar()) != EOF&&c != ' '&&c != '\n')
        sum = sum * 10 + c - '0';
    return sum;
}

    相关文章

      网友评论

          本文标题：(原创PAT乙级1085 PAT单位排行)

          本文链接：https://www.haomeiwen.com/subject/bcadeqtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|(原创PAT乙级1085 PAT单位排行)|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！