題目
1085 PAT單位排行 （25 分）
每次 PAT 考試結束后抠艾，考試中心都會發(fā)布一個考生單位排行榜。本題就請你實現這個功能。
輸入格式：
輸入第一行給出一個正整數 N（≤10的5次方）缰泡，即考生人數。隨后 N 行代嗤，每行按下列格式給出一個考生的信息：
準考證號 得分 學校
其中準考證號是由 6 個字符組成的字符串棘钞，其首字母表示考試的級別：B代表乙級，A代表甲級干毅，T代表頂級宜猜；得分是 [0, 100] 區(qū)間內的整數；學校是由不超過 6 個英文字母組成的單位碼（大小寫無關）硝逢。注意：題目保證每個考生的準考證號是不同的姨拥。
輸出格式：
首先在一行中輸出單位個數绅喉。隨后按以下格式非降序輸出單位的排行榜：
排名 學校 加權總分 考生人數
其中排名是該單位的排名（從 1 開始）；學校是全部按小寫字母輸出的單位碼叫乌；加權總分定義為乙級總分/1.5 + 甲級總分 + 頂級總分*1.5的整數部分柴罐；考生人數是該屬于單位的考生的總人數。
學校首先按加權總分排行憨奸。如有并列革屠，則應對應相同的排名，并按考生人數升序輸出排宰。如果仍然并列似芝，則按單位碼的字典序輸出。
思考過程
做題過程中板甘，咋看上去邏輯很簡單党瓮，做起來卻在某個點里想了好久，代碼也隨之更換了幾次版本盐类，這個點就是map的思想寞奸，一開始有考慮map，但是不想這么快就用傲醉，想想用以往的知識是否可以代替這個功能蝇闭。
先說說我的解題邏輯：
根據題目要求，建立學校結構體硬毕，包含著學校名字呻引，各考試類型分數，還有總分和該校的考試人數吐咳，并建立該結構體數組逻悠。
1.每錄入一個學生的考試類型，成績和學校名字韭脊，然后根據其考試類型童谒，計入該學生所屬學校的總分。
2.上面錄完全部學生信息沪羔，這時學校的總分和考試人數信息也搞完了饥伊，接著就是排序，按照題目的要求來排序蔫饰，這里我試過了兩種排序琅豆，一個stl的sort，另一種是自己寫的堆排序篓吁，結果是前者略快一點茫因，唉
3.輸出
這里唯一令我嘗試了多種方法的是怎么讓錄入已經重復學校的信息能盡快找出來對應的，其實就是map功能杖剪。
主要分成三次嘗試
第一次嘗試冻押，計算學校名字字符串的hash值驰贷，自定義的，二十六進制洛巢，6位括袒，理論上程序是走得通，或者小量數據也可稿茉，但是乘法原理就是加法箱熬，十萬個數據，數組空間達到了3E以上狈邑，每算一個學生的學校名字時候一直用乘法計算它的hash值，在最后測試點內存超限了蚤认，果然不行米苹。
第二次嘗試，我嘗試再第一次的基礎上改進砰琢，減少乘法蘸嘶，并且減少空間，采用之前學過的鏈地址法+3位二十六進制+對比后三位字符串陪汽，每發(fā)現新的就重新開辟一個训唱，理論上程序也是走得通，或者小量數據也可挚冤，但是測試點就是這么神奇况增，你開辟空間太多次了，倒數第二個測試點就運行超時训挡，估計這個測試點澳骤，讓我的hash重復率高導致開辟次數達到上萬次，這的確耗時澜薄，比較傷心为肮，當然你可以把全空間預先全部覆蓋好，弄成二維數組肤京，第一維的維數會高達上萬颊艳，空間浪費太大，加上鏈地址法上查找也會按照O(n)時間復雜度查找忘分，已經達不到map的功能棋枕。然后我又想嘗試投石問路，把二十六進制推進到4位又或者3位26進制+后三位的ASCII值饭庞，但覺得此時在此題浪費時間過多了戒悠，不想繼續(xù)了，日后再想想舟山。
第三次嘗試绸狐，基于這個查找的特點卤恳，我只需要查重而已，直接啟用C++的unordered_map寒矿，來代替自定義計算hash值突琳，其余邏輯沒變，通過...
unordered_map內部實現了一個哈希表（也叫散列表符相，通過把關鍵碼值映射到Hash表中一個位置來訪問記錄拆融，查找的時間復雜度可達到O(1)，其在海量數據處理中有著廣泛應用）
優(yōu)點： 因為內部實現了哈希表啊终，因此其查找速度非常的快
缺點： 哈希表的建立比較耗費時間
一刷代碼
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.統(tǒng)計學校的總分
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.統(tǒng)計學校的總分
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.統(tǒng)計學校的總分
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;
}
