[伯俊]問題推奨システムバージョン1#21939
説明:
2つの
C++プール
maxHeap
とminHeap
を同時に管理する問題.2つの
Heap
のsyncを計算し、arr
を検査に残し、削除されたかどうかを判断します.C++プール
#include <bits/stdc++.h>
using namespace std;
int arr[100001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
priority_queue<pair<int, int>> maxHeap;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
int N; cin >> N;
for (int i=0; i<N; i++) {
int P, L;
cin >> P >> L;
maxHeap.push({ L, P });
minHeap.push({ L, P });
arr[P] = L;
}
int M; cin >> M;
for (int i=0; i<M; i++) {
string cmd; int n1, n2;
cin >> cmd; cin >> n1;
if (cmd == "add") {
cin >> n2;
arr[n1] = n2;
maxHeap.push({ n2, n1 });
minHeap.push({ n2, n1 });
}
else if (cmd == "recommend") {
if (n1 == 1) {
while(maxHeap.top().first != arr[maxHeap.top().second]) maxHeap.pop();
cout << maxHeap.top().second << '\n';
}
else if (n1 == -1) {
while(minHeap.top().first != arr[minHeap.top().second]) minHeap.pop();
cout << minHeap.top().second << '\n';
}
}
else if (cmd == "solved") {
arr[n1] = 0;
}
}
return 0;
}
Reference
この問題について([伯俊]問題推奨システムバージョン1#21939), 我々は、より多くの情報をここで見つけました https://velog.io/@ahu8867/백준-문제-추천-시스템-Version-1-21939テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol