题源：https://www.patest.cn/contests/pat-a-practise/1141
本文同时发布于个人博客
注意，对于最后两个测试点，使用 Python 语言会超时，从前三个测试点来看，同样的逻辑下 Python 的速度大概是 C++ 的 14%，嗯，太慢了……
OK，那么，照例，（好吧，这是我第一次有机会写 PAT 的解题过程，没有前例^_^）
先看题目：
After each PAT, the PAT Center will announce the ranking of institutions based on their students' performances. Now you are asked to generate the ranklist.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=10^5), which is the number of testees. Then N lines follow, each gives the information of a testee in the following format:
ID Score School
where "ID" is a string of 6 characters with the first one representing the test level: "B" stands for the basic level, "A" the advanced level and "T" the top level; "Score" is an integer in [0, 100]; and "School" is the institution code which is a string of no more than 6 English letters (case insensitive). Note: it is guaranteed that "ID" is unique for each testee.
Output Specification:
For each case, first print in a line the total number of institutions. Then output the ranklist of institutions in nondecreasing order of their ranks in the following format:
Rank School TWS Ns
where "Rank" is the rank (start from 1) of the institution; "School" is the institution code (all in lower case); "TWS" is the total weighted score which is defined to be the integer part of"ScoreB/1.5 + ScoreA + ScoreT*1.5", where "ScoreX" is the total score of the testees belong to this institution on level X; and "Ns" is the total number of testees who belong to this institution.
The institutions are ranked according to their TWS. If there is a tie, the institutions are supposed to have the same rank, and they shall be printed in ascending order of Ns. If there is still a tie, they shall be printed in alphabetical order of their codes.
限制
- 时间限制：500ms
- 内存限制：65537kB
输入输出要求
题目大概意思就是说，对于每次 PAT 考试，我们会对每个学校进行排名。
- 输入格式是
N，ID Score School - 输出格式是
N，Rank School TWS Ns
其中： - N 是队伍总数（N<=100000）
- M 是学校总数
- ID 是一个定长 6 个字符的字符串，第一位取值范围：'T', 'A', 'B'
- Score 是该 ID 队伍的成绩
- School 就是学校名称了是一个不定长的字符串
- Rank 是排名，注意题目要求：非递减——就是可以连续相同的 rank，数学上可以叫驻点
- TWS 是学校的总成绩，计算公式：
ScoreB/1.5 + ScoreA + ScoreT*1.5，这里的 Score[TAB] 对应上面 ID 的第一位 [TAB] - Ns 是学校参赛队伍数量
排序规则：
首先按照 TWS 递减排序。
如果 TWS 相同，按照 Ns 递增排序。
如果 Ns 相同，按照学校名称的字母表顺序排序
啊哈，看到这道题有什么思路吗？
- 看到这道题应该有的大致思路：
- 使用字典（哈希表）来保存
学校名和学校 - 读取数据到字典(Complexity: O(N));
- 对字典，按照要求，进行排序(Complexity: O(2NlogN) or worst: O(2N^2));
- 输出，这里要注意排名（rank）的显示要求——非递减;
- 使用字典（哈希表）来保存
- 想说其实这道题思路并不难，但是这道题的确花了我不少时间，因为最后两个测试点（5 points）总是超时。就算使用 Cpp unoredered_map 的处理时间也接近了 490ms，好悬。10^5 的数据量不敢小觑。
- 一开始选择数据结构的时候，我使用了标准库的 map 结构，大概可以当做一个红黑树。所以不管什么插入删除操作大概都是 O(logN) 的复杂度，这个复杂度太高了。后来改用 unorderd_map 结构，也即是哈希表，嗯，插入的时间复杂度接近 O(1) 了，很好。这里要感谢一下 Cpp 标准库，从 map 迁移到 unordered_map 只改了两处类型签名而已，非常方便。
- 为了让代码结构清晰，我设立了两个类，一个是 School 一个是 Result。
- Result 中只有一个成员变量，其类型是： unordered_map<string, School*>
- 在 School 中，存放了学校的名称、总成绩、队伍数。值得提一下的是：为了避免冗余的强制类型转换 (double) -> (long) 我使用一个惰性计算的技巧，即增加一个成员变量 long sc，在调用 get_score() 的时候才计算出 sc 的值，而如果 sc 已经被计算过了，那就直接返回 sc 的值。也算是一点点优化吧。
- 其他的比如说 cin 缓慢的问题（cin 会判断输入类型是否匹配，会比 scanf 慢），就没时间改了，如果有兴趣自己改改吧，也不难。
照例，
Cpp 代码如下：
#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;
//#define DEBUG
namespace My {
#ifdef DEBUG
long cntlog = 0;
template <class Tp>
inline void log(Tp x, string lv = "INFO") {
My::cntlog++;
std::cout << "--> " << lv << " " << x << std::endl;
}
#endif
#ifndef DEBUGs
template <class Tp>
inline void log(Tp x, ...) {}
#endif
}
class School { // Class for saving status of each institution
string name;
int counter;
double score;
long sc; // save time, for the convertion from double to long is somehow expensive
public:
School(string &name, double score, char level) {
this->name = name;
this->counter = 0;
this->score = 0;
this->sc = -1;
this->append(score, level);
}
School* append(double score, char level) {
this->counter++;
double lv = 1.0;
if (level == 'B')
lv = 2.0 / 3.0;
else if (level == 'T')
lv = 1.5;
this->score += score * lv;
return this;
}
int get_counter() const {
return this->counter;
}
long long get_score() {
if(this->sc == -1){
this->sc = long(this->score); // In the test case as the `Sample Input`, this line will be hit 5 times
}
return this->sc; // and this line will be hit 49 times. So this `lazy initial tech` should save some time.
}
string get_name() const {
return this->name;
}
};
class Result { // Class for saving the result, containing an unordered map of <school name, School>
unordered_map <string, School*> d;
public:
void append(string school_name, int score, char level) {
if (d.find(school_name) == d.end())
d.insert(pair <string, School*> (school_name, new School(school_name, score, level)));
else
d[school_name]->append(score, level);
}
vector<pair<string, School*>>& sort() { // sort function. use a lambda to customize, and return a sorted vector. It will take most of the time.
auto cmp = [&](const pair <string, School*> &lhs, const pair <string, School*> &rhs) -> bool {
if (lhs.second->get_score() == rhs.second->get_score()) {
if (lhs.second->get_counter() == rhs.second->get_counter())
return lhs.second->get_name() < rhs.second->get_name();
else
return lhs.second->get_counter() < rhs.second->get_counter();
} else{
return lhs.second->get_score() > rhs.second->get_score();
}
};
vector<pair<string, School*>> *vec = new vector<pair<string, School*>>(this->d.begin(), this->d.end());
std::sort(vec->begin(), vec->end(), cmp);
return *vec;
}
};
int main() {
int N;
cin >> N;
Result* res = new Result();
while (N--) {
char level[7];
int score;
string name;
cin >> level >> score >> name;
char lv = level[0];
transform(name.begin(), name.end(), name.begin(), ::tolower); // transform the school name to lower case
res->append(name, score, lv); // append to the result (as an unordered map)
}
vector<pair<string, School*>> r = res->sort(); // sort the result and return a vector
unsigned long n = r.size();
cout << n << endl;
unsigned long cnt = 1, i = 0;
for (auto iter = r.begin(); iter != r.end(); iter++) { // <-○
i++; // ↑
if (iter != r.begin() and iter->second->get_score() != (iter - 1)->second->get_score()) { // calculate the rank of each institution (Complexity: O(1), so the outer for loop should be O(N))
cnt = i;
}
cout << cnt << " " << iter->second->get_name() << " " << iter->second->get_score() << " " << iter->second->get_counter() << endl;
}
return 0;
}
Python 代码如下：(代码短，容易理解。逻辑和 C++ 代码一样，只是最后两个测试点超时)
class School:
name = ''
score = 0
counter = 0
def __init__(self, school_name, score, level):
self.name = school_name
self.append(score, level)
def append(self, score, level):
self.counter += 1
lv = 1
if level == 'B':
lv = 2/3
elif level == 'T':
lv = 1.5
self.score += score * lv
return self
def set_score_to_int(self):
self.score = int(self.score)
return self
if __name__ == '__main__':
s = int(input())
d = {}
for i in range(s):
t = input().split(' ')
level = t[0][0]
score = int(t[1])
school_name = t[2].lower()
if school_name in d.keys():
d[school_name].append(score, level)
else:
d[school_name] = School(school_name, score, level)
d = sorted(d.items(), key=lambda x: [-x[1].score, x[1].counter, x[0]]) # Could cost most of the time
print(len(d))
cnt = 1
for i in range(len(d)):
if i > 0 and int(d[i][1].score) != int(d[i-1][1].score):
cnt = i+1
print("{0} {1} {2} {3}".format(cnt, d[i][1].name, int(d[i][1].score), d[i][1].counter))
