本文为PAT甲级分类汇编系列文章。
排序题，就是以排序算法为主的题。纯排序，用 std::sort 就能解决的那种，20分都算不上，只能放在乙级，甲级的排序题要么是排序的规则复杂，要么是排完序还要做点什么的。
在1051至1100中有6道：
| 题号 | 标题 | 分数 | 大意 | 时间 |
| 1055 | The World's Richest | 25 | 限定范围排序结果 | 500ms |
| 1056 | Mice and Rice | 25 | 分组排序 | 200ms |
| 1062 | Talent and Virtue | 25 | 一定规则的排序 | 400ms |
| 1075 | PAT Judge | 25 | 复杂排序 | 200ms |
| 1080 | Graduate Admission | 30 | 志愿与录取 | 250ms |
| 1083 | List Grades | 25 | 限定范围排序结果 | 400ms |
选了1056、1075和1080 3道做，其他不做是因为觉得太水了。
1056：
题目要求模拟晋级赛，每组选手中的最高分进入下一组，同一轮中淘汰的名次相同。
边界情况是只剩一个人，这时比赛就结束了，是循环的结束条件，所以也不算边界的坑了。
主循环中用到两个 std::vector<int> 对象，分别作为当前一轮的选手与晋级的选手，在循环的最后一个赋值一个清空。非常巧的是（也可能是必然），输入数据中的顺序刚好可以表示当前一轮。
很简单的题，一遍就AC了。
#include <iostream>
#include <vector>
#include <algorithm> struct Programmer
{
int index;
int mice;
int score;
int rank;
}; int main(int argc, char const *argv[])
{
int total, per;
std::cin >> total >> per;
std::vector<Programmer> prog(total);
for (int i = ; i != total; ++i)
prog[i].index = i, std::cin >> prog[i].mice;
std::vector<int> current(total);
for (int i = ; i != total; ++i)
std::cin >> current[i]; std::vector<int> next;
while ()
{
auto iter = current.begin();
int index;
while (iter != current.end())
{
int max = -;
for (int i = ; i != per && iter != current.end(); ++i, ++iter)
if (prog[*iter].mice > max)
{
index = *iter;
max = prog[*iter].mice;
}
++prog[index].score;
next.push_back(index);
}
if (next.size() == )
break;
current = next;
next.clear();
} std::sort(prog.begin(), prog.end(), [](const Programmer& lhs, const Programmer& rhs) {
return lhs.score > rhs.score;
});
int count = ;
prog.front().rank = ;
for (auto iter = prog.begin() + ; iter != prog.end(); ++iter, ++count)
if (iter->score == (iter - )->score)
iter->rank = (iter - )->rank;
else
iter->rank = count;
std::sort(prog.begin(), prog.end(), [](const Programmer& lhs, const Programmer& rhs) {
return lhs.index < rhs.index;
});
auto end = prog.end() - ;
for (auto iter = prog.begin(); iter != end; ++iter)
std::cout << iter->rank << ' ';
std::cout << end->rank << std::endl; return ;
}
1075：
这道题要求模拟PAT评分系统，统计一系列提交，最后按照用户来输出。麻烦的是没有提交、编译错误、满分等情况，之前看到这道题的时候就觉得太烦跳了。
要排好序，主要要搞清楚题目里的这些概念：总分、满分题数、有效用户，还有提交与输出分数的关系。
一个个来讲吧。总分就是所有分数加起来，这很简单。然而，由于-1表示编译错误的存在，累加不能直接相加，要判断是否大于0（大于等于也一样）。同时还需要一种表示没有提交过的方法，我就用-2了。
满分题数，就是把一个人的各题分数一个个和满分比较，所有相等的数量。这是排序中的第二关键字。
有效用户，就是有过编译通过的提交的用户。就算提交完是0分，也算有效用户，这个点坑到了。
提交与分数，坑在如果提交编译错误，这道题是算0分而不是算没提交，这个也坑到了。
区区一道25分题就放那么多坑，我下午放学开始写，晚上熄灯后才写完（虽然没有一直在写，至少加起来也一个多小时了，但主要是不AC我难受啊），姥姥你心不痛吗？
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm> int num_problem;
std::vector<int> problem_full; class User
{
public:
User(int _id)
: id_(_id), problems(num_problem, -)
{
;
}
void submission(int _pro, int _score)
{
if (_score > problems[_pro])
problems[_pro] = _score;
}
bool operator<(const User& _user) const
{
calculate();
_user.calculate();
if (score_ > _user.score_)
return true;
if (score_ < _user.score_)
return false;
if (perfect_ > _user.perfect_)
return true;
if (perfect_ < _user.perfect_)
return false;
return id_ < _user.id_;
}
bool valid() const
{
calculate();
return valid_;
}
void rank(int _rank)
{
rank_ = _rank;
}
int rank() const
{
return rank_;
}
int score() const
{
calculate();
return score_;
}
friend std::ostream& operator<<(std::ostream& _os, const User& _user);
private:
int id_;
std::vector<int> problems;
mutable bool calculated_;
mutable int score_;
mutable int perfect_;
mutable bool valid_;
int rank_;
void calculate() const
{
if (!calculated_)
{
calculated_ = true;
for (int i = ; i != problems.size(); ++i)
if (problems[i] >= )
{
score_ += problems[i];
if (problems[i] == problem_full[i])
++perfect_;
valid_ = true;
}
}
}
}; std::ostream& operator<<(std::ostream& _os, const User& _user)
{
std::cout << std::setfill('');
_os << _user.rank_ << ' ';
_os << std::setw() << _user.id_ << ' ';
_os << _user.score_;
for (int s : _user.problems)
{
std::cout << ' ';
if (s >= )
std::cout << s;
else if (s == -)
std::cout << '';
else
std::cout << '-';
}
return _os;
} int main(int argc, char const *argv[])
{
int num_user;
int num_submission;
std::cin >> num_user >> num_problem >> num_submission; std::vector<User> users;
users.reserve(num_user);
for (int i = ; i != num_user; ++i)
{
users.emplace_back(i + );
}
problem_full.reserve(num_problem);
for (int i = ; i != num_problem; ++i)
{
int t;
std::cin >> t;
problem_full.push_back(t);
}
for (int i = ; i != num_submission; ++i)
{
int user, pro, score;
std::cin >> user >> pro >> score;
--user;
--pro;
users[user].submission(pro, score);
}
std::sort(users.begin(), users.end());
int count = ;
users.front().rank(count++);
for (auto iter = users.begin() + ; iter != users.end(); ++iter, ++count)
{
if (iter->score() == (iter - )->score())
iter->rank((iter - )->rank());
else
iter->rank(count);
}
for (const auto& u : users)
if (u.valid())
std::cout << u << std::endl;
else
break; return ;
}
为了优雅，我把代码写得很OO（其实是object-based）。虽然也没有人会去复用它。
还有一点，测试数据里的case 4很诡异，我提交了3次，时间分别是191、110、194ms。更关键的是这道题限制就200ms，我要是再写烂一点不就超时了吗？还一会超时一会不超时的，搞不懂。
1080：
这道题要求模拟志愿录取，核心算法在于分配而不是排序，之前读题的时候没注意，给分到这里来了。
输入、排序、输出都很简单，难在分配，即所谓录取过程。要是没有并列的都要录取这条规则，对排序完的学生遍历一遍就可以了，但它偏要有这条，不过谁让它是30分题呢。讲真，我感觉这道30分比上一道25分简单，一遍AC。
我解决并列问题的方法是这样的：一对iterator，分别指向并列一段的起始和尾后，然后将学校名额“锁住”，保持它是否有空余名额的状态，这时往里塞。就算超名额也不管，是题目要求的。“锁住”以后也不用“解锁”，下次“锁住”的时候会更新状态（也许应该换个名字，毕竟lock以后不unlock怪怪的）。
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <utility>
using std::rel_ops::operator>; struct School
{
int quota;
std::vector<int> admitted;
bool free()
{
return free_;
}
void lock()
{
free_ = admitted.size() < quota;
}
private:
bool free_;
}; struct Student
{
int id;
int grade_e;
int grade_i;
std::vector<int> choices;
int rank;
bool operator<(const Student& _rhs) const
{
if (grade_e + grade_i < _rhs.grade_e + _rhs.grade_i)
return true;
if (grade_e + grade_i > _rhs.grade_e + _rhs.grade_i)
return false;
return grade_e < _rhs.grade_e;
}
bool operator==(const Student& _rhs) const
{
return grade_e == _rhs.grade_e && grade_i == _rhs.grade_i;
}
}; int main()
{
int num_applicant, num_school, num_choice;
std::cin >> num_applicant >> num_school >> num_choice;
std::vector<School> schools(num_school);
std::vector<Student> students(num_applicant);
for (auto& s : schools)
std::cin >> s.quota;
for (int i = ; i != num_applicant; ++i)
{
auto& s = students[i];
s.id = i;
std::cin >> s.grade_e >> s.grade_i;
s.choices.resize(num_choice);
for (auto& i : s.choices)
std::cin >> i;
}
std::sort(students.begin(), students.end(), std::greater<Student>());
for (auto iter = students.begin() + ; iter != students.end(); ++iter)
if (*iter == *(iter - ))
iter->rank = (iter - )->rank;
else
iter->rank = (iter - )->rank + ;
auto end = students.begin();
while (end != students.end())
{
auto iter = end;
while (end != students.end() && *end == *iter)
++end;
for (auto& s : schools)
s.lock();
for (; iter != end; ++iter)
{
for (const auto& s : iter->choices)
if (schools[s].free())
{
schools[s].admitted.push_back(iter->id);
break;
}
}
}
for (auto& s : schools)
{
std::sort(s.admitted.begin(), s.admitted.end());
if (!s.admitted.empty())
{
auto end = s.admitted.end() - ;
for (auto iter = s.admitted.begin(); iter != end; ++iter)
std::cout << *iter << ' ';
std::cout << *end;
}
std::cout << std::endl;
}
}
自己用 operator< 来实现 operator> 太烦了，我选择 std::rel_ops 。
还有一个星期就要考了，我10篇才写了3篇，可以不用睡觉了。