牛客 新建 Microsoft Office Word 文档 （模拟+优先队列）

题目描述
CSL正在学习《计算机办公自动化》文件的建立与删除。

CSL发现，当他新建一个word文档时，会得到一个名为"新建 Microsoft Office Word 文档.doc"的文件，再新建一个，则名为"新建 Microsoft Office Word 文档(2).doc"，再新建，便是"新建 Microsoft Office Word 文档(3).doc"。不断新建，编号不断递增。倘若他已经新建了三个文档，然后删除了"新建 Microsoft Office Word 文档(2).doc"，再新建一个就又会得到一个"新建 Microsoft Office Word 文档(2).doc"。

严格来说，Windows在每次新建文档时，都会选取一个与已有文件编号不重复的最小正整数作为新文档的编号。

现在，请你编程模拟以上过程，支持以下两种操作：

New：新建一个word文档，反馈新建的文档的编号；

Delete id：删除一个编号为id的word文档，反馈删除是否成功。

初始时一个文件都没有，“新建 Microsoft Office Word 文档.doc"的编号算作1。
输入描述:
第一行一个正整数n表示操作次数，接下来n行，每行表示一个操作。若该行为"New”，则表示新建，为:Delete id"则表示要删除编号为id的文档，其中id为一个正整数。操作按输入顺序依次进行。操作次数不超过100000，删除编号的数值不超过100000。
输出描述:
对于输入的每一个操作，输出其反馈结果。对于新建操作，输出新建的文档的编号；对于删除操作，反馈删除是否成功：如果删除的文件存在，则删除成功，输出"Successful"，否则输出"Failed"。

输入
12
New
New
New
Delete 2
New
Delete 4
Delete 3
Delete 1
New
New
New
Delete 4

输出
1
2
3
Successful
2
Failed
Successful
Successful
1
3
4
Successful

题目分析：
刚开始就觉得这是一个简单的模拟题，然后我就按照题目的意思模拟了一遍，一交，，，咳咳咳，通过率80%，我就觉得这个题目有点猫腻，一看题解，优先队列！！！

优先队列代码

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> >q; //定义一个小根堆储存被删除的元素，方便后序使用
char c[100];
const int maxn = 1e5 + 10;
int vis[maxn];
int main()
{
   
	int n, cnt = 0;
	scanf("%d", &n);
	while (n--)
	{
   
		scanf("%s", c);
		if (c[0] == 'N')
		{
   
			if (q.empty()) //如果队列为空，就说明可以一直创建新的文档
			{
   
				printf("%d\n", ++cnt);
				vis[cnt] = 1; //标记使用过了
			}
			else //如果队列不为空，说明存在比当前数还小的数字
			{
   
				int x = q.top(); //取队列的头部
				q.pop();
				printf("%d\n", x); //输出队列的头部元素
				vis[x] = 1;		   //并且标记使用过了
			}
		}
		else
		{
   
			int y;
			scanf("%d", &y);
			if (vis[y]) //如果当前元素已经创建了那么就可以删除
			{
   
				puts("Successful");
				q.push(y);	//把删除的元素放入队列
				vis[y] = 0; //并且清空标记
			}
			else
				puts("Failed");
		}
	}
	return 0;
}

Set代码

#include <bits/stdc++.h>
using namespace std;
set<int> s;
const int maxn = 1e5 + 10;
char c[maxn];
int vis[maxn];
int main()
{
   
	int n, cnt = 0;
	scanf("%d", &n);
	while (n--)
	{
   
		scanf("%s", c);
		if (c[0] == 'N')
		{
   
			if (s.empty())
			{
   
				printf("%d\n", ++cnt);
				vis[cnt] = 1;
			}
			else
			{
   
				auto it = s.begin();
				printf("%d\n", *it);
				vis[*it] = 1;
				s.erase(it);
			}
		}
		else
		{
   
			int y;
			scanf("%d", &y);
			if (vis[y])
			{
   
				puts("Successful");
				vis[y] = 0;
				s.insert(y);
			}
			else
				puts("Failed");
		}
	}
	return 0;
}