https://www.acmicpc.net/problem/21939
21939번: 문제 추천 시스템 Version 1
tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령
www.acmicpc.net
최소 힙과 최대 힙을 구현해서 해결하자.
하나의 구조체로 두 개의 힙을 만들기 때문에
연산자 오버로딩은 못쓴다.
<소스코드>
|
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
|
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m;
int pos[200010];
bool visited[200010];
struct node {
int bango, nando, idx;
};
struct max_compare {
bool operator()(const node n1, const node n2)
{
if (n1.nando == n2.nando)
{
return n1.bango < n2.bango;
}
return n1.nando < n2.nando;
}
};
struct min_compare {
bool operator()(const node n1, const node n2)
{
if (n1.nando == n2.nando)
{
return n1.bango > n2.bango;
}
return n1.nando > n2.nando;
}
};
priority_queue<node, vector<node>, max_compare> max_pq;
priority_queue<node, vector<node>, min_compare> min_pq;
int main()
{
memset(visited, false, sizeof(visited));
memset(pos, 0, sizeof(pos));
cin >> n;
for (int i = 1; i <= n; i++)
{
node n;
cin >> n.bango >> n.nando;
visited[i] = true;
pos[n.bango] = i;
n.idx = i;
max_pq.push(n);
min_pq.push(n);
}
cin >> m;
for (int i = 1; i <= m; i++)
{
string s;
int x, y;
cin >> s;
if (s == "add")
{
cin >> x >> y;
node tmp;
tmp.bango = x;
tmp.nando = y;
tmp.idx = n + i;
max_pq.push(tmp);
min_pq.push(tmp);
visited[n + i] = true;
pos[tmp.bango] = n + i;
}
else if (s == "recommend")
{
cin >> x;
// 가장 어려운 문제 추천
if (x == 1)
{
while (true)
{
auto tmp = max_pq.top();
if (visited[tmp.idx])
{
cout << tmp.bango << '\n';
break;
}
max_pq.pop();
}
}
// 가장 쉬운 문제 추천
else if (x == -1)
{
while (true)
{
auto tmp = min_pq.top();
if (visited[tmp.idx])
{
cout << tmp.bango << '\n';
break;
}
min_pq.pop();
}
}
}
else if (s == "solved")
{
cin >> x;
int idx = pos[x];
visited[idx] = false;
}
}
}
|
cs |
'Heap & 우선순위 큐' 카테고리의 다른 글
| Social Media (0) | 2024.02.12 |
|---|---|
| 카드 정렬하기 (1) | 2024.02.11 |
| 뉴스 알림 (0) | 2024.02.06 |
| 중간값 구하기 (0) | 2024.01.18 |
| 가희와 프로세스 1 (0) | 2023.11.16 |
