新建 Microsoft Office Word 文档 STL

description：

对于文档有两个操作
1.新建 编号取当前最小的没有用过的值 从1开始计算
2.删除 删除对应编号
询问每次新建的编号

solution：

容易想到先用bool来表示当前编号是否使用 但是正向维护当前已经使用的编号查询最小未使用的编号有些困难
用一个优先队列或者set来维护被删除过的编号 这样可以O(1)得到答案 满足题目复杂度

code:

#include <bits/stdc++.h>

using namespace std;

set <int> s;

bool vis[100005];

int main(){
    ios::sync_with_stdio(0);

    int n ;cin >> n;

    int cnt = 0;
    string op;

    while(n --){
        cin >> op;

        if(op [0] == 'N'){
            if(s.empty()){
                cout << ++ cnt ;
               vis[cnt] = 1;
            }else{
                auto it = s.begin();
                cout << *it ;
                vis[*it] = 1;
                s.erase(it);
            }
        }else{
            int x;cin >> x;
            if(vis[x]){
                vis[x] = 0;
                s.insert(x);
                cout << "Successful";
            }else{
                cout << "Failed";
            }
        }
        cout << '\n';
    }

    return 0;
}