题目
链接：https://ac.nowcoder.com/acm/contest/28886/1015
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld题目描述
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
题解
在这道题目里要反其道而行,我仅仅需要记录在插入之后删除的,这样才好找到空闲的位置
这道题目有两个解题方法
- 使用priority_queue:在优先队列里边扔进去空缺的位置,用数组标记是不是空缺
new过程:logN 或者 1;
delete过程:log N或者1; - 使用set(treeset)[可以支持自定义排序还有标准排序]
相比于优先队列的优势与不足
- 使用它也仅仅是为了找到最小值,它的功能没有被放大
- 如果硬生生地使用set的查找功能,则不必创建数组,但是它的时间复杂度会变成log N
在这道题目里边,反其道而行,但是不会增添额外的时间开销,是因为有index来划分范围.
set别有洞天
set可以进行自定义排序!!!(但是它默认是用最小值排的)
struct cmp {
bool operator () (const int a,const int b)const
{
return a < b;
}
};代码
我为了锻炼set,使用set来搞事情,同时,牺牲一点时间复杂度,抛弃使用数组来存储
#include <iostream>
#include <set>
using namespace std;
struct cmp {
bool operator () (const int a,const int b)const
{
return a < b;
}
};
set<int, cmp>st;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int index = 0;//使用索引来划定一下范围,不然的话,要把所有没有新建的都搞进set,有点划不来
int T;
cin >> T;
while (T--)
{
char s[12];
cin >> s;
if (s[0] == 'N')//新建
{
if (st.empty())
{
index++;
cout << index << endl;
}
else
{
auto it = st.begin();
cout << *it << endl;
st.erase(it);
}
}
else//删除
{
int in;
cin >> in;
if (in > index)
{
cout << "Failed" << endl;
}
else
{
auto it = st.find(in);
if (it == st.end())//存在这个元素
{
cout << "Successful" << endl;
st.insert(in);
}
else//这个元素已经被删除
{
cout << "Failed" << endl;
}
}
}
}
return 0;
}