题解：P13857 [SWERC 2020] Gratitude

· · 题解

Sol.

题目是英文题面，这里先给出 Google 翻译过后的题面：

题面：

题目描述

本听说了埃蒙斯和麦卡洛的研究表明，刻意练习感恩会对人们的幸福感产生持久的影响。因为他也想拥有幸福，所以他决定每天结束时回顾过去的一天，并写下三件让他感恩的事情，每行一件。在练习了 N 天之后，他很想知道哪些事情在他的清单上出现次数最多。帮助本找出他最常感恩的 K 件事。

输入格式

输入以一行开始，包含两个空格分隔的整数，N 和 K，按此顺序排列。接下来是 3 \times N 行，包含本 N 天的笔记。你可以假设对应同一天的三行记录不重复。也就是说，如果将输入分成 N 个连续 3 行的块，则没有一个块包含两行相同的记录。

限制

1≤K≤3 \times N≤100000

每行输入最多包含 50 个 ASCII 字符。

输出格式

输出应为 Ben 感激之事的列表，按其在 Ben 列表中出现的频率排序（频率最高的项目排在最前面）。如果两个项目的频率相同，则最近的项目应排在最前面。也就是说，如果出现次数相同，则输入中最后出现较晚的项目应在输出中更早出现。最后，如果 Ben 的列表中包含超过 K 个不同的项目，则输出应仅包含前 K 个项目（按照要求的顺序）。

分析：

由于题目要求存储 string 类型与两个 int 类型配对，自然而然就想到用 map 类型来存储。（你想用 struct ？好啊，没人拦着你！TLE 了就老实了）

然而，map 类型还是有许多的坑的，稍有不注意就会掉进去。

坑点 1：

map 类型不可用 sort！

由于 （语言研发人认为）map 类型默认有序，就不能用 sort 了！（吐槽 ing）

坑点 2：

map 类型的迭代器不可以被加一个整数！

mp.begin()+i，mp.begin()+3 这种用法全部都是错的！

言归正传。

我们创建一个结构体 node，存储要用到的计算出现次数的变量 cnt、计算最后一次出现在什么位置的变量 id。

struct node {
    int id, cnt;
    static node ton(int a, int b) { // 构造函数
        node tmp;
        tmp.cnt = a;
        tmp.id = b;
        return tmp;
    }
};

然后，创建一个 map 类型“数组”

map <string, node> a;

之后写好一个极其复杂的比较函数 \operatorname{cmp}：

bool cmp(pair <string, node> a, pair <string, node> b) {
    if (a.second.cnt != b.second.cnt) {
        return a.second.cnt > b.second.cnt;
    } else {
        return a.second.id > b.second.id;
    }
}

接下来是主函数部分，没有什么要讲的，我直接放全部代码吧：

#include <bits/stdc++.h>
using namespace std;
struct node {
    int id, cnt;
    static node ton(int a, int b) { // 构造函数
        node tmp;
        tmp.cnt = a;
        tmp.id = b;
        return tmp;
    }
};
map <string, node> a;
string tmp;
bool cmp(pair <string, node> a, pair <string, node> b) {
    if (a.second.cnt != b.second.cnt) {
        return a.second.cnt > b.second.cnt;
    } else {
        return a.second.id > b.second.id;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    cin.ignore(); // 清除换行符，避免 getline 读错字符
    for (int i = 0; i < 3 * n; i++) {
        getline(cin, tmp);
        if (a.find(tmp) != a.end()) { // 找到了
            a[tmp].cnt++;
            a[tmp].id = i;
        } else { // 没找到
            a.insert(make_pair(tmp, node::ton(1, i))); // map 类型用 pair 实现
        }
    }
    vector <pair <string, node> > v(a.begin(), a.end()); // map 类型不可用 sort，于是用 vector 来排序
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < min((int) (v.size()), k)/*避免越界*/; i++) {
        cout << v[i].first << endl;
    }
    return 0;
}

完结撒花

（求过 QwQ）