题解：P13857 [SWERC 2020] Gratitude

· · 题解

题目大意：

给定 3N 个字符串，输出出现次数最多的 K 个字符串，如果出现次数相同，则最后一次出现的位置靠后的在前。

题目思路：

这道题不算太难，主要就是输出的这一部分。

首先我们可以用一个 map 来存一下字符串的信息，它的值为一个二元组，表示出现次数和最后出现的位置。

接着我们用一个结构体数组来存下这些数据，这样是为了方便排序和输出，排序的函数其实照着题面说的写就行了。

最后排完序了，我们就输出。注意，有时候可能没有 K 个互不相同的字符串，那我们就按照规则全部输出。

还有一个细节就是在输入字符串前要吃掉换行符，否则会有问题。

总体思路还是挺简单的，代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, k, top;
struct node { //结构体数组存数据
    string str;
    int pos, total;
} a[100010];
string s[100010];
map <string, pair <int, int> > mp; //map存信息
bool cmp (node x, node y) { //排序函数
    if (x.total != y.total) return x.total > y.total;
    return x.pos > y.pos;
}
int main () {
    cin >> n >> k;
    getline (cin, s[0]); //吃掉换行符
    for (int i = 1; i <= n * 3; i ++) { 
        getline (cin, s[i]); //输入
        mp[s[i]].second ++; //更新信息
        mp[s[i]].first = i;
    }
    for (auto& [u, v] : mp) { //将map的数据复制进结构体数组
        top ++;
        a[top].str = u;
        a[top].pos = v.first;
        a[top].total = v.second;
    }
    sort (a + 1, a + top + 1, cmp); //进行排序
    for (int i = 1; i <= min (top, k); i ++) //输出
        cout << a[i].str << '\n';
}