- it
- 1129 Recommendation System
题目大意
类似于操作系统中LRU（最近最少使用算法）。给出用户最近浏览记录，根据访问频数让你列出他接下来最有可能访问的K项，按照可能性递减，如果可能性相同则按索引升序。
思路解析
题目本身不难，如果对C++和容器操作掌握不好可就很难了……（没错，说的就是我……） 为了排序和唯一性自然想到set，set中的元素是复杂类型node，必须提供大小比较机制，所以必然要在类内部重载<操作符。（这在以往的PAT中从未考察过） 紧接着就是set查找，所给元素必须用参数列表声明对象作为参数。 然后就是常规的操作了，具体请看代码。
示例代码
#include<iostream>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
using namespace std
;
struct node
{
public:
int id
, count
;
bool operator<(const node
&nod
) const {
return count
!= nod
.count
? count
> nod
.count
:id
< nod
.id
;
}
};
vector
<int> lib(50010);
int main() {
int n
, k
,id
;
scanf("%d %d", &n
, &k
);
set
<node
> se
;
vector
<node
> vec
;
for (int i
= 0; i
< n
; i
++) {
scanf("%d", &id
);
if (i
!= 0) {
printf("%d:", id
);
int count
= 0;
for (auto it
= se
.begin(); it
!= se
.end() && count
< k
; it
++) {
printf(" %d", (*it
).id
);
count
++;
}
printf("\n");
}
auto it
= se
.find(node
{ id
,lib
[id
] });
if (it
!= se
.end()) {
se
.erase(it
);
lib
[id
]++;
}
lib
[id
]++;
se
.insert(node
{ id
,lib
[id
] });
}
return 0;
}
