ν(Queue)
λ¬Έμ
https://www.acmicpc.net/problem/1966
1966λ²: νλ¦°ν° ν
λ¬Έμ μ¬λ¬λΆλ μλ€μνΌ μ¬λ¬λΆμ νλ¦°ν° κΈ°κΈ°λ μ¬λ¬λΆμ΄ μΈμνκ³ μ νλ λ¬Έμλ₯Ό μΈμ λͺ λ Ήμ λ°μ ‘μμλλ‘’, μ¦ λ¨Όμ μμ²λ κ²μ λ¨Όμ μΈμνλ€. μ¬λ¬ κ°μ λ¬Έμκ° μμΈλ€λ©΄ Queue μλ£οΏ½οΏ½
www.acmicpc.net
#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
11279λ²: μ΅λ ν
첫째 μ€μ μ°μ°μ κ°μ N(1≤N≤100,000)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ μ°μ°μ λν μ 보λ₯Ό λνλ΄λ μ μ xκ° μ£Όμ΄μ§λ€. λ§μ½ xκ° μμ°μλΌλ©΄ λ°°μ΄μ xλΌλ κ°μ λ£λ(μΆκ°νλ) μ°μ°μ΄κ³ , xκ° 0μ΄λΌλ©΄ λ°°μ΄μμ κ°μ₯ ν° κ°μ μΆλ ₯νκ³ κ·Έ κ°μ λ°°μ΄μμ μ κ±°νλ κ²½μ°μ΄λ€. μ λ ₯λλ μμ°μλ 2^31λ³΄λ€ μλ€.
www.acmicpc.net
#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
1927λ²: μ΅μ ν
첫째 μ€μ μ°μ°μ κ°μ N(1≤N≤100,000)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ μ°μ°μ λν μ 보λ₯Ό λνλ΄λ μ μ xκ° μ£Όμ΄μ§λ€. λ§μ½ xκ° μμ°μλΌλ©΄ λ°°μ΄μ xλΌλ κ°μ λ£λ(μΆκ°νλ) μ°μ°μ΄κ³ , xκ° 0μ΄λΌλ©΄ λ°°μ΄μμ κ°μ₯ μμ κ°μ μΆλ ₯νκ³ κ·Έ κ°μ λ°°μ΄μμ μ κ±°νλ κ²½μ°μ΄λ€. μ λ ₯λλ μμ°μλ 2^31λ³΄λ€ μλ€.
www.acmicpc.net
#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
11286λ²: μ λκ° ν
첫째 μ€μ μ°μ°μ κ°μ N(1≤N≤100,000)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ μ°μ°μ λν μ 보λ₯Ό λνλ΄λ μ μ xκ° μ£Όμ΄μ§λ€. λ§μ½ xκ° 0μ΄ μλλΌλ©΄ λ°°μ΄μ xλΌλ κ°μ λ£λ(μΆκ°νλ) μ°μ°μ΄κ³ , xκ° 0οΏ½
www.acmicpc.net
#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
1715λ²: μΉ΄λ μ λ ¬νκΈ°
μ λ ¬λ λ λ¬Άμμ μ«μ μΉ΄λκ° μλ€κ³ νμ. κ° λ¬Άμμ μΉ΄λμ μλ₯Ό A, BλΌ νλ©΄ λ³΄ν΅ λ λ¬Άμμ ν©μ³μ νλλ‘ λ§λλ λ°μλ A+B λ²μ λΉκ΅λ₯Ό ν΄μΌ νλ€. μ΄λ₯Όν λ©΄, 20μ₯μ μ«μ μΉ΄λ λ¬Άμκ³Ό 30μ₯οΏ½οΏ½
www.acmicpc.net
#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
1655λ²: κ°μ΄λ°λ₯Ό λ§ν΄μ
첫째 μ€μλ μλΉμ΄κ° μΈμΉλ μ μμ κ°μ Nμ΄ μ£Όμ΄μ§λ€. Nμ 1λ³΄λ€ ν¬κ±°λ κ°κ³ , 100,000λ³΄λ€ μκ±°λ κ°μ μμ°μμ΄λ€. κ·Έ λ€μ Nμ€μ κ±Έμ³μ μλΉμ΄κ° μΈμΉλ μ μκ° μ°¨λ‘λλ‘ μ£Όμ΄μ§λ€. μ μλ -10,000λ³΄λ€ ν¬κ±°λ κ°κ³ , 10,000λ³΄λ€ μκ±°λ κ°λ€.
www.acmicpc.net
#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';
}
}