PAT 甲级 刷题日记|A 1129 Recommendation System (25 分)

access 访问 通道 存取 进入 机会

思路

这道题的关键是选取合适的数据结构，方便的排序+随机的存取，使用集合最为方便。

代码

#include <bits/stdc++.h>
using namespace std;

int n, k;
const int maxn = 50003;
int book[maxn];
struct node{
    int data;
    int fre;
    node(int d, int f): data(d), fre(f) {
    }
    bool operator < (const node &a) const {
        if (fre != a.fre) return fre > a.fre;
        return data < a.data;
    }
};


int main() {
    cin>>n>>k;
    set<node> Node;
    for (int i = 0; i < n; i++) {
        int num;
        cin>>num;
        if (i != 0) {
            cout<<num<<":";
            int temp = 0;
            for (auto th = Node.begin(); th != Node.end() && temp < k; th++) {
                cout<<" "<<th->data;
                temp++;
            }
            cout<<endl;
        }
        auto it = Node.find(node(num, book[num]));
        if (it != Node.end()) Node.erase(it);
        book[num]++;
        Node.insert(node(num, book[num]));
    }
}