新建 Microsoft Office Word 文档(模拟 set)

新建 Microsoft Office Word 文档

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

思路

用set去存没有用过的编号，每次new只需要取begin然后删掉，delete就查询是否在集合里就行了，查询的操作可以用空间换时间，用一个bool数组去同步set

代码1(set)

//新建 Microsoft Office Word 文档(模拟 set) 
#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;

int main()
{
 	set<int> s;
 	for(int i = 0 ; i < N ; i++)
 		s.insert(i + 1);
 	
 	int n;
 	scanf("%d" , &n);
 	getchar();
 	
 	while(n--)
 	{
		int id;
		char str[8];
		scanf("%s %d" , str , &id);
		
		if(str[0] == 'N')
		{
			printf("%d\n" , *s.begin());
			s.erase(s.begin());
		}
		else
		{
			if(s.count(id) != 0)
				puts("Failed");
			else
			{
				s.insert(id);
				puts("Successful");
			}
		}
	}
	return 0; 
}

代码2(set + 数组优化)

//新建 Microsoft Office Word 文档(模拟 set bool数组优化查询) 
#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;

bool used[N];

int main()
{
 	set<int> s;
 	for(int i = 0 ; i < N ; i++)
 		s.insert(i + 1);
 	
 	int n;
 	scanf("%d" , &n);
 	getchar();
 	
 	while(n--)
 	{
		int id;
		char str[8];
		scanf("%s %d" , str , &id);
		
		if(str[0] == 'N')
		{
			printf("%d\n" , *s.begin());
			used[*s.begin()] = true;
			s.erase(s.begin());
		}
		else
		{
			if(!used[id])
				puts("Failed");
			else
			{
				s.insert(id);
				used[id] = false;
				puts("Successful");
			}
		}
	}
	return 0; 
}

牛客算法竞赛入门课第二节习题题解文章被收录于专栏

入门课第二节习题题解