PAT-BASIC1085——PAT单位排行PAT-ADVANCED1141——PAT Ranking of Institutions

我的PAT-BASIC代码仓：https://github.com/617076674/PAT-BASIC

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：

PAT-BASIC1085：https://pintia.cn/problem-sets/994805260223102976/problems/994805260353126400

PAT-ADVANCED1141：https://pintia.cn/problem-sets/994805342720868352/problems/994805344222429184

题目描述：

PAT-BASIC1085：

PAT-ADVANCED1141：

知识点：排序

思路：定义一个结构体来保存学校信息

学校名称需要统一转换为大写或者小写进行比较。

时间复杂度是O(nlogn)，其中n为学校总数。空间复杂度是O(N)。

C++代码：

#include<iostream> #include<map> #include<string> #include<vector> #include<algorithm> using namespace std; struct school{ int rank; string name; int score[3]; //score[0]代表scoreB, score[1]代表score[A], score[2]代表score[T] int TWS; int Ns; }; map<string, school> schoolMap; bool cmp(school s1, school s2); int main(){ int N; scanf("%d", &N); string ID, schoolName; int score; for(int i = 0; i < N; i++){ cin >> ID >> score >> schoolName; for(int i = 0; i < schoolName.length(); i++){ if(schoolName[i] >= 'A' && schoolName[i] <= 'Z'){ schoolName[i] = schoolName[i] - 'A' + 'a'; } } if(schoolMap.find(schoolName) == schoolMap.end()){ school tempSchool; tempSchool.name = schoolName; if(ID[0] == 'B'){ tempSchool.score[0] = score; tempSchool.score[1] = 0; tempSchool.score[2] = 0; }else if(ID[0] == 'A'){ tempSchool.score[1] = score; tempSchool.score[0] = 0; tempSchool.score[2] = 0; }else{ tempSchool.score[2] = score; tempSchool.score[0] = 0; tempSchool.score[1] = 0; } tempSchool.Ns = 1; schoolMap[schoolName] = tempSchool; }else{ if(ID[0] == 'B'){ schoolMap[schoolName].score[0] += score; }else if(ID[0] == 'A'){ schoolMap[schoolName].score[1] += score; }else{ schoolMap[schoolName].score[2] += score; } schoolMap[schoolName].Ns++; } } vector<school> schools; for(map<string, school>::iterator it = schoolMap.begin(); it != schoolMap.end(); it++){ it->second.TWS = it->second.score[0] * 1.0 / 1.5 + it->second.score[1] + it->second.score[2] * 1.5; schools.push_back(it->second); } sort(schools.begin(), schools.end(), cmp); schools[0].rank = 1; for(int i = 1; i < schools.size(); i++){ if(schools[i].TWS == schools[i - 1].TWS){ schools[i].rank = schools[i - 1].rank; }else{ schools[i].rank = i + 1; } } cout << schools.size() << endl; for(int i = 0; i < schools.size(); i++){ cout << schools[i].rank << " " << schools[i].name << " " << schools[i].TWS << " " << schools[i].Ns << endl; } } bool cmp(school s1, school s2){ if(s1.TWS == s2.TWS){ if(s1.Ns == s2.Ns){ return s1.name < s2.name; }else{ return s1.Ns < s2.Ns; } }else{ return s1.TWS > s2.TWS; } }

C++解题报告：