CodeForces 681C Heap Operations (模拟题，优先队列)

题意：给定 n 个按顺序的命令，但是可能有的命令不全，让你补全所有的命令，并且要求让总数最少。

析：没什么好说的，直接用优先队列模拟就行，insert，直接放入就行了，removeMin，就得判断一下队列是不是空的，然后再考虑getMin,这个是不是对应的值，如果队列中首元素比它大，那么就加上一个，

如果相等直接取出，如果小于就不断取队列中最小元素。

代码如下：

#include <bits/stdc++.h>

using namespace std;

char s[15], t[30];

vector<string> ans;

int main(){

    int n, x;

    while(cin >> n){

        ans.clear();

        priority_queue<int, vector<int>, greater<int> > q;

        for(int i = 0; i < n; ++i){

            scanf("%s", s);

            if(s[0] == 'i'){

                scanf("%d", &x);

                sprintf(t, "insert %d", x);

                ans.push_back(string(t));

                q.push(x);

            }

            else if(s[0] == 'r'){

                if(q.empty()){

                    ans.push_back("insert 1");

                    q.push(1);

                }

                ans.push_back("removeMin");

                q.pop();

            }

            else{

                scanf("%d", &x);

                while(true){

                    if(q.empty() || q.top() > x){

                        q.push(x);

                        sprintf(t, "insert %d", x);

                        ans.push_back(string(t));

                    }

                    else if(q.top() == x){  break; }

                    else{

                        ans.push_back("removeMin");

                        q.pop();

                    }

                }

                sprintf(t, "getMin %d", x);

                ans.push_back(string(t));

            }

        }

        printf("%d\n", ans.size());

        for(int i = 0; i < ans.size(); ++i)

            cout << ans[i] << endl;

    }

    return 0;

}

巴特西

CodeForces 681C Heap Operations (模拟题，优先队列)

最新文章

热门文章