【CSP-201909】推荐系统

数据结构题,也可以说是STL题。

由操作三我们可以想到用m个set(平衡树)来分别维护不同分类的产品的优先度。查询的实现就用一个prority_queue(堆),初始时把每个非空分类下的第一个产品扔到堆里,每次取堆头加入答案并把该产品所在分类的下一个产品加入堆。用迭代器就可以实现。

但是操作一和二我们用上述方法的话就无法快速增删,于是我们再用m个unordered_map(哈希表)来对每个分类所有产品位于set中的迭代器进行索引,增删的时候就直接通过迭代器操作。虽说C++不建议保存迭代器,但既然是做题就不管这么多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;

struct product
{
int type, id, score;
product(int _type, int _id, int _score)
{
type = _type;
id = _id;
score = _score;
}

struct cmp
{
bool operator()(const product &o1, const product &o2)
{
if (o1.score != o2.score)
return o1.score > o2.score;
else if (o1.type != o2.type)
return o1.type < o2.type;
else
return o1.id < o2.id;
}
};
};

vector<set<product, product::cmp>> type_to_product;
vector<unordered_map<int, set<product, product::cmp>::iterator>> type_id_to_iter;
int m, n;

void add_product(int type, int id, int score)
{
auto iter = type_to_product[type].emplace(type, id, score).first;
type_id_to_iter[type][id] = iter;
}
void remove_product(int type, int id)
{
type_to_product[type].erase(type_id_to_iter[type][id]);
type_id_to_iter[type].erase(id);
}
void perform_ask(int k, vector<int> caps, vector<vector<product>> &ans)
{
struct cmp
{
bool operator()(const set<product, product::cmp>::iterator &o1, const set<product, product::cmp>::iterator &o2)
{
return !product::cmp()(*o1, *o2);
}
};
priority_queue<set<product, product::cmp>::iterator, vector<set<product, product::cmp>::iterator>, cmp> pq;

ans.resize(m);
for (auto v : ans)
v.clear();

for (int i = 0; i < m; i++)
if (!type_to_product[i].empty())
pq.push(type_to_product[i].begin());

while (k && !pq.empty())
{
auto iter = pq.top();
pq.pop();

if (caps[iter->type])
{
ans[iter->type].push_back(*iter);
caps[iter->type]--;
k--;

if (++iter != type_to_product[iter->type].end())
pq.push(iter);
}
}
}

int main()
{
ios::sync_with_stdio(false);
cin >> m >> n;
type_to_product.resize(m);
type_id_to_iter.resize(m);
for (int j = 1; j <= n; j++)
{
int id, score;
cin >> id >> score;
for (int i = 0; i < m; i++)
add_product(i, id, score);
}

int t;
cin >> t;
while (t--)
{
int opt;
cin >> opt;
if (opt == 1)
{
int type, id, score;
cin >> type >> id >> score;
add_product(type, id, score);
}
else if (opt == 2)
{
int type, id;
cin >> type >> id;
remove_product(type, id);
}
else if (opt == 3)
{
int k;
vector<int> caps(m);
cin >> k;
for (int i = 0; i < m; i++)
cin >> caps[i];

vector<vector<product>> ans;
perform_ask(k, caps, ans);
for (auto v : ans)
{
if (v.size() > 0)
{
for (auto p : v)
cout << p.id << ' ';
cout << endl;
}
else
cout << -1 << endl;
}
}
}
return 0;
}
Author: ssttkkl
Link: https://ssttkkl.github.io/CSP/2019/12/%E3%80%90CSP-201909%E3%80%91%E6%8E%A8%E8%8D%90%E7%B3%BB%E7%BB%9F/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.