题目很简单,主要通过这题学习一下STL如何自定义排序规则。
通常,需要自定义排序规则的STL有:set、priority_queue、map。
这些都是可以通过写一个排序对象来实现的。
例如:
set<int, CMP> st
set<PII, CMP> st
priority_queue<int, CMP> que
priority_queue<PII, vector<PII>, CMP> que
map<int, int, CMP> mp
然后排序对象这样写,即重载()运算符:
struct CMP {
bool operator()(const PII &x, const PII &y) const {
...
}
};
struct CMP {
bool operator()(const int &x, const int &y) const {
...
}
}
然后,在程序中访问STL内部元素有两种方法:
for (auto x : STL)
for (auto it = STL.begin(); it != STL.end(); it++)
最后,是这题的代码:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 10;
struct CMP {
bool operator()(const PII &x, const PII &y) const {
if (x.second == y.second) return x.first < y.first;
return x.second > y.second;
}
};
int n, k;
set<PII, CMP> a;
unordered_map<int, int> cnt;
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
if (a.size()) {
cout << t << ": ";
int tim = 0;
for (auto it = a.begin(); it != a.end(); it++) {
cout << (it->first) << ' ';
if (++tim == k) break;
}
cout << endl;
}
a.erase({t, cnt[t]});
a.insert(make_pair(t, ++cnt[t]));
}
return 0;
}