CF19A World Football Cup 题解

myster1ous · 2022-03-14 21:33:21 · 题解

题目传送门

题目大意

有 n 支球队和 \frac{(n - 1)n}{2} 场比赛，排序规则即得分（赢球加 3 分，平局加 1 分，输球不加不减。）为第一关键字，净胜球为第二关键字，进球数为第三关键字。（注，净胜球为赢球数 - 输球数），前 \frac{n}{2} 的队伍可以进淘汰赛，让你求出可以进淘汰赛的队伍（按球队名的字典序排序）。

数据范围

解题思路

我们先建一个球队的类，这样就可以使用 sort 进行快速排序。

class Team{
    public:
        int score, win, get; // score为得分，win为净胜球，get为进球数
        string name;
        Team(int s, int w, int g): score(s), win(w), get(g){};
        Team(): score(0), win(0), get(0){};
        bool operator<(const Team& a) const&;
} t[maxn]; // maxn = 64
bool Team::operator<(const Team& a) const& {
// 重载小于号，以分数为第一关键字，净胜球为第二关键字，进球数为第三关键字
    if (score != a.score)
        return score > a.score;
    else if (win != a.win)
        return win > a.win;
    else
        return get > a.get;
}

接下来还是大模拟，输入队伍名称，得分，然后统计，这里可以用一个 unordered_map 来建立队伍名和下标的映射关系。

这里的 unordered_map 和 map 是很相似的，区别是 unordered_map 内部不排序，底层是哈希表，还有一个最重要的区别就是：

unordered_map 时间复杂度期望为 O(1) !

然后我们就可以求出每一个球队的分数，净胜球和进球数了！

最后，只需要将前 \frac{n}{2} 个团队的名字取出来，再排个序，就可以了！

附 AC 代码:

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <vector>
#define maxn 64
using namespace std;
class Team{
    public:
        int score, win, get; // score为得分，win为净胜球，get为进球数
        string name;
        Team(int s, int w, int g): score(s), win(w), get(g){};
        Team(): score(0), win(0), get(0){};
        bool operator<(const Team& a) const&;
} t[maxn];
int n;
unordered_map<string, int> teams;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> t[i].name;
    for (int i = 1; i <= n; i++)    
        teams[t[i].name] = i;
    int m = n * (n - 1) / 2;
    for (int i = 1; i <= m; i++) {
        int in1, in2;
        string name1, name2;
        string s;
        char ch;
        cin >> s >> in1 >> ch >> in2;// 直接使用 cin 读入
        name1 = s.substr(0, s.find('-')); // 在s中的子串即为name1, name2.
        name2 = s.substr(s.find('-') + 1);
        if (in1 == in2) {
            t[teams[name1]].score += 1;
            t[teams[name2]].score += 1;
        } else if (in1 < in2)
            t[teams[name2]].score += 3;
        else
            t[teams[name1]].score += 3;
        t[teams[name1]].win += in1 - in2;
        t[teams[name2]].win += in2 - in1;
        t[teams[name1]].get += in1;
        t[teams[name2]].get += in2;
    }
    sort(t + 1, t + n + 1);
    vector<string> v;
    for (int i = 1; i <= n / 2; i++)
        v.push_back(t[i].name); // 取出前 n/2 个球队的名字
    sort(v.begin(), v.end()); // sort对string默认就是字典序排序
    for (auto i : v)
        cout << i << "\n";
    return 0;
}
bool Team::operator<(const Team& a) const& {
// 重载小于号，以分数为第一关键字，净胜球为第二关键字，进球数为第三关键字
    if (score != a.score)
        return score > a.score;
    else if (win != a.win)
        return win > a.win;
    else
        return get > a.get;
}

无注释版代码

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <vector>
#define maxn 64
using namespace std;
class Team{
    public:
        int score, win, get;
        string name;
        Team(int s, int w, int g): score(s), win(w), get(g){};
        Team(): score(0), win(0), get(0){};
        bool operator<(const Team& a) const&;
} t[maxn];
int n;
unordered_map<string, int> teams;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> t[i].name;
    for (int i = 1; i <= n; i++)    
        teams[t[i].name] = i;
    int m = n * (n - 1) / 2;
    for (int i = 1; i <= m; i++) {
        int in1, in2;
        string name1, name2;
        string s;
        char ch;
        cin >> s >> in1 >> ch >> in2;
        name1 = s.substr(0, s.find('-'));
        name2 = s.substr(s.find('-') + 1);
        if (in1 == in2) {
            t[teams[name1]].score += 1;
            t[teams[name2]].score += 1;
        } else if (in1 < in2)
            t[teams[name2]].score += 3;
        else
            t[teams[name1]].score += 3;
        t[teams[name1]].win += in1 - in2;
        t[teams[name2]].win += in2 - in1;
        t[teams[name1]].get += in1;
        t[teams[name2]].get += in2;
    }
    sort(t + 1, t + n + 1);
    vector<string> v;
    for (int i = 1; i <= n / 2; i++)
        v.push_back(t[i].name);
    sort(v.begin(), v.end());
    for (auto i : v)
        cout << i << "\n";
    return 0;
}
bool Team::operator<(const Team& a) const& {
    if (score != a.score)
        return score > a.score;
    else if (win != a.win)
        return win > a.win;
    else
        return get > a.get;
}