欢迎访问我的pat甲级题解目录哦https://blog.csdn.net/richenyunqi/article/details/84981078

题目描述

题意分析

用户每想购买一件商品，就向他推荐K个商品，这K个商品从他从前的购买过的商品中按照购买次数从高到低的顺序选择K个，如果有购买次数相同的，就按照商品的编号从小到大排序。

算法分析

定义一个50005的数组m存储每个商品的购买过的次数。定义一个类T，包含商品的编号、购买次数，并按排序要求重载小于运算符。定义一个set<T>s，对购买过的商品进行自动排序。对当前要购买的物品，先按要求输出s中前K个商品，然后对当前购买物品的购买次数进行递增，在s中查找当前购买的物品的对象，并将其删除，将更新之后的当前购买物品及其购买次数压入s中。

C++代码

#include<bits/stdc++.h> using namespace std; struct T{//商品类 int indice=0,frequency=0;//商品编号、商品购买次数 T(int i,int f):indice(i),frequency(f){}//构造函数 bool operator <(const T&t)const{//重载小于运算符 return this->frequency!=t.frequency?this->frequency>t.frequency:this->indice<t.indice; } }; int m[50005];//存储物品购买次数 set<T>s; int main(){ int N,K,a; scanf("%d%d%d",&N,&K,&a); s.insert(T(a,1));//将第一个物品压入s中 ++m[a];//递增第一个物品购买次数 for(int i=2;i<=N;++i){ scanf("%d",&a); printf("%d: ",a); int k=0; for(auto i=s.cbegin();i!=s.cend()&&k<K;++i){//输出s中前K个物品 printf("%s%d",i!=s.cbegin()?" ":"",i->indice); ++k; } printf("\n"); auto it=s.find(T(a,m[a])); if(it!=s.end())//查找s中是否含当前物品，如果包含，则进行删除 s.erase(it); s.insert(T(a,++m[a]));//将更新后的商品及其购买次数压入s } return 0; }

题意分析：

用户每想购买一件商品，就向他推荐K个商品，这K个商品从他从前的购买过的商品中按照购买次数从高到低的顺序选择K个，如果有购买次数相同的，就按照商品的编号从小到大排序。