ν(Queue)
λ¬Έμ
https://www.acmicpc.net/problem/1966
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
queue<pair<int, bool>> q;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
if (i == m)
q.push(make_pair(v[i], true));
else
q.push(make_pair(v[i], false));
}
sort(v.begin(), v.end());
int result = 0;
while (!q.empty()) {
if (q.front().first == v.back()) {
result++;
v.pop_back();
if (q.front().second) {
cout << result << '\n';
break;
}
}
else
q.push(q.front());
q.pop();
}
}
}
μ°μ μμ ν(Priority Queue)
top, popμμ μΆμΆλλ μμλ μ μΌ λ¨Όμ λ€μ΄μ¨ κ°μ΄ μλ νμ¬ μ°μ μμ ν μμμ μ μΌ μ°μ μμκ° λμ μμμ΄λ€.
λ³΄ν΅ ν(Heap) μλ£κ΅¬μ‘°λ‘ ꡬνλλ€.
λ¬Έμ
https://www.acmicpc.net/problem/11279
#include <iostream>
#include <queue>
using namespace std;
int main(void)
{
int n;
cin >> n;
// less<int>κ° μλ΅λ μν
// ν° κ²λΆν° λ½λλ€.
priority_queue<int> q;
while (n--) {
int x;
cin >> x;
if (x == 0) {
if (q.empty())
cout << "0\n";
else {
cout << q.top() << "\n";
q.pop();
}
}
else
q.push(x);
}
}
https://www.acmicpc.net/problem/1927
#include <iostream>
#include <queue>
using namespace std;
int main(void)
{
int n;
cin >> n;
// μμ κ²λΆν° λ½λλ€.
priority_queue<int, vector<int>, greater<int>> q;
while (n--) {
int x;
cin >> x;
if (x == 0) {
if (q.empty())
cout << "0\n";
else {
cout << q.top() << "\n";
q.pop();
}
}
else
q.push(x);
}
}
https://www.acmicpc.net/problem/11286
#include <iostream>
#include <queue>
using namespace std;
struct compare {
bool operator()(int a, int b) {
if (abs(a) == abs(b))
return a > b;
return abs(a) > abs(b);
}
};
int main(void)
{
int n;
cin >> n;
priority_queue<int, vector<int>, compare> q;
while (n--) {
int x;
cin >> x;
if (x == 0) {
if (q.empty())
cout << "0\n";
else {
cout << q.top() << "\n";
q.pop();
}
}
else
q.push(x);
}
}
https://www.acmicpc.net/problem/1715
#include <iostream>
#include <queue>
using namespace std;
int num[10001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0, tmp; i < N; ++i) {
cin >> tmp;
pq.push(tmp);
}
int ans = 0;
while (!pq.empty()) {
int tmp = pq.top();
pq.pop();
if (!pq.empty()) {
tmp += pq.top();
pq.pop();
ans += tmp;
pq.push(tmp);
}
}
cout << ans;
}
https://www.acmicpc.net/problem/1655
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int n, m;
cin >> n;
priority_queue<int> low; // μ€κ°κ°κ³Ό μμ μ
priority_queue<int, vector<int>, greater<int>> high; // ν° μ
while (n--) {
cin >> m;
// κ·μΉ1. low.size() >= high.size()
if (low.size() > high.size())
high.push(m);
else
low.push(m);
// κ·μΉ2. low.top() <= high.top()
if (!high.empty() && !low.empty() && low.top() > high.top()) {
int a = high.top(), b = low.top();
high.pop(), low.pop();
high.push(b), low.push(a);
}
cout << low.top() << '\n';
}
}