关于c++:PAT甲级1129-Recommendation-System

题目粗心

依据用户每次点击的货色的编号，输入他在点以后编号之前应该给这个用户举荐的商品的编号，只举荐 k 个，也就是输入用户已经点击过的商品编号的最多的前 k 个，如果恰好两个商品有雷同的点击次数，就输入编号较小的那个。

算法思路

这里依据题意很显著在每一次输出商品编号的时候须要依据排序后的后果输入举荐产品的编号，然而应用 sort 进行排序肯定会超时，所以应用 set 汇合的主动排序功能，排序根据的是商品的编号 val 和之前呈现的频率，所以将这两个属性封装为一个构造体 Commodity, 并且重载小于号，使得在每一次增加商品后就会依照自定义的排序规定进行排序。在每一次输出的时候，只有不是第一次点击商品，那么就输入 set 汇合中前 k 个商品的音讯，而后再将以后商品增加到 set 汇合中，因为该商品可能曾经呈现在了 set 汇合中，所以要先查找以后商品并删除，而后再将新的商品音讯增加其中。查找商品的办法就是应用 num 数组统计曾经增加进 set 汇合中的每一个商品编号对应的频率，而后将以后商品的编号和频率封装为 Commodity，而后在 set 汇合中查找即可。

提交后果

AC 代码

#include <cstdio>
#include <set>
#include <cstring>

using namespace std;

struct Commodity{
    int val;
    int fre;
    bool operator < (Commodity node) const{return this->fre!=node.fre?this->fre>node.fre:this->val<node.val;}
    Commodity(int _val, int _fre){
        val = _val;
        fre = _fre;
    }
};

int main() {
    int n,k;
    scanf("%d %d",&n,&k);
    set<Commodity> s;
    int num[n+1];// 统计每一个数字呈现的频率
    memset(num,0,sizeof(num));
    for(int i=1;i<=n;++i){
        int query;
        scanf("%d",&query);
        if(i!=1){printf("%d:",query);
            // 只有不是第一个数字就输入汇合 s 中前 k 个数字
            int cnt = 0;
            for(auto it:s){if(cnt<k){printf("%d",it);
                    ++cnt;
                }else{break;}
            }
            printf("\n");
        }
        // 增加以后数字到汇合中
        Commodity toBeFound = Commodity{query, num[query]};
        auto it = s.find(toBeFound);
        if(s.find(toBeFound)!=s.end()){
            // 以后数字在 s 汇合中呈现过
            s.erase(it);
        }
        ++num[query];
        s.insert(Commodity{query, num[query]});
    }
    return 0;
}