NC17889 新建 Microsoft Office Word 文档 set暴力

链接：https://ac.nowcoder.com/acm/problem/17889
来源：牛客网

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"。

示例1
输入
复制

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

题意:

要求模拟操作:

• 选择最小的空位插入一个数字
• 删除一个位置 $idx$idx的数字
• • 删除成功输出成功
• • 删除失败输出失败

思路

• 用 set<int>存储所有空位(最多 $1e5$1e5),
• 删除 $k$k时去判断 $set$set里是否有空位 $k$k,有就失败, 反之成功
• 同理,插入一个数字时,应该删除 $set$set里的最小的位置(set.begin())
• 也可以用堆来维护空位,加个 $vis\left[\right]$vis[ ]标记即可

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

int n, m, Q, K, idx;
bool vis[MAXN];

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%d ", &Q);
	n = MAXN;
	set<int> ety; //存储所有空位
	
	//开始时,所有空位都存在
	for(int i=1; i<=n; i++) ety.insert(i);
	
	while(Q--) {
		char cmd[16];
		idx = 1;
		scanf("%s ", cmd);
		if(cmd[0] == 'D') {
			scanf("%d ", &idx);
			if(ety.find(idx) != ety.end()) {
				printf("Failed\n"); //无法删除,因为ety里有空位idx
			} else { //可以删除idx
				//记得把空位idx加入set
				ety.insert(idx);
				printf("Successful\n");
			}
		} else {
			printf("%d\n", *ety.begin());
			//插入了最小的空位,所以删除
			ety.erase(ety.begin());
		}
	}

#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}