Решение задачи Операции с кучей с Codeforces

Без пояснения   Просмотров: 277


Недавно Петя начал изучать структуру данных «Двоичная куча».

Куча, с которой он работает, позволяет выполнять следующие операции:

добавить число в кучу;
узнать минимальное число в куче;
удалить минимальное число из кучи.
Таким образом, в любой момент куча содержит в себе набор чисел (возможно, пустой), среди которых, возможно, есть одинаковые.

Код

#include <iostream>
#include <queue>
#include <string>

using namespace std;

const int NO_X = 2e9;

const string REMOVE = "removeMin";
const string GET = "getMin";
const string INSERT = "insert";

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<pair<string, int> > ans;
    priority_queue<int> q;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == INSERT) {
            int x;
            cin >> x;
            q.push(-x);
            ans.push_back(make_pair(s, x));
        } else if (s == GET) {
            int x;
            cin >> x;
            while (!q.empty() && -q.top() < x) {
                q.pop();
                ans.push_back(make_pair(REMOVE, NO_X));
            }
            if (q.empty() || -q.top() > x) {
                q.push(-x);
                ans.push_back(make_pair(INSERT, x));
            }
            ans.push_back(make_pair(s, x));
        } else { // s == REMOVE
            if (q.empty()) {
                ans.push_back(make_pair(INSERT, 0));
            } else {
                q.pop();
            }
            ans.push_back(make_pair(s, NO_X));
        }
    }

    cout << ans.size() << "\n";
    for (auto& p : ans) {
        cout << p.first;
        if (p.second != NO_X) {
            cout << " " << p.second;
        }
        cout << "\n";
    }


    return 0;
}

         

Администратор Photo Автор: Администратор


Код

from sys import stdin
input = stdin.readline
from heapq import heappop, heappush

n = int(input())
arr = [input() for _ in range(n)]
res, q = [], []

for s in arr:
    if s[0] == 'i':
        heappush(q, int(s.split()[1]))
    elif s[0] == 'g':
        val = int(s.split()[1])
        while q and q[0] < val:
            res.append('removeMin')
            heappop(q)
        if not q or q[0] > val:
            res.append('insert ' + s.split()[1])
            heappush(q, val) 
    else:
        if q: heappop(q)
        else: res.append('insert 1')
    res.append(s)

print(len(res))
print("\n".join(res))

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться