试题 算法提高 新建Microsoft Word文档
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
L正在出题，新建了一个word文档，想不好取什么名字，身旁一人惊问：“你出的题目叫《新建Microsoft Word文档》吗？”，L大喜，一拍桌子，说：“好，就叫这个名字了。”
仔细观察，当你新建一个word文档时，会得到一个名为“新建 Microsoft Word 文档.doc”的文件，再新建一个，则名为“新建 Microsoft Word 文档(2).doc”，再新建，便是“新建 Microsoft Word 文档(3).doc”。不断新建，编号不断递增。倘若你现在新建了三个文档，然后删除了“新建 Microsoft Word 文档(2).doc”，再新建就又会得到一个“新建 Microsoft Word 文档(2).doc”。
严格说，Windows在每次新建文档时，都会选取一个与已有文件编号不重复的最小正整数作为新文档的编号。
请编程模拟以上过程，支持以下两种操作
New：新建一个word文档，反馈新建的文档的编号
Delete id：删除一个编号为id的word文档，反馈删除是否成功
初始时一个文件都没有，“新建 Microsoft Word 文档.doc”的编号算作1。
输入格式
第一行一个正整数n表示操作次数，接下来n行，每行表示一个操作。若该行为”New”，则表示新建，为”Delete id”则表示要删除编号为id的文档，其中id为一个正整数。操作按输入顺序依次进行。
输出格式
对于输入的每一行，输出其反馈结果。对于新建操作，输出新建的文档的编号；对于删除操作，反馈删除是否成功：如果删除的文件存在，则删除成功，输出”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
数据规模和约定
操作次数（即输入的行数）不超过1481
删除编号的数值不超过2012
解题思路：模拟。
代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF -65535
vector<int> vkt;
vector<int> res;
void findEmptyMin(){
//cout<<"start to findEmptyMin"<<endl;
if(vkt.empty()){
vkt.push_back(1);
res.push_back(1);
}
else{
if(vkt[0]!=1){
vkt.push_back(1);
res.push_back(1);
}
else{
int pos=-1;
for(int i=0;i<vkt.size()-1;i++){
if( (vkt[i]+1) != vkt[i+1] ){
pos=i;
break;
}
}
if(pos!=-1){// 若 最小值 为缺
int curV=vkt[pos]+1;
vkt.push_back(curV);
res.push_back(curV);
sort(vkt.begin(),vkt.end());
}
else{ //若 最小值 在vkt.end() 后
int curV=vkt[ vkt.size()-1 ]+1;
vkt.push_back(curV);
res.push_back(curV);
}
}
}
}
void SingleOpt(string order){
// cout<<"start to SingleOpt"<<endl;
char io;
int no;
if(order=="New"){
io='n';
}
if(order=="Delete"){
cin>>no;
io='d';
}
// cout<<"before switch"<<endl;
switch(io){
case 'n':{
findEmptyMin();
break;
}
case 'd':{//若删除
vector<int>::iterator it=find(vkt.begin(),vkt.end(),no);
if(it==vkt.end()){ // 若没找到
res.push_back(-1);// -1 表示 删除失败
}
else{
it=vkt.erase(it);
res.push_back(0);// 0 表示 删除成功
}
break;
}
}
sort(vkt.begin(),vkt.end());
// cout<<"SingleOpt is over"<<endl;
}
int main(int argc, char** argv) {
int n;
cin>>n;
for(int i=0;i<n;i++){
string order;
cin>>order;
SingleOpt(order);
}
for(int i=0;i<res.size();i++){
if(res[i]>0)
cout<<res[i]<<endl;
else if(res[i]==0)
cout<<"Successful"<<endl;
else if(res[i]==-1)
cout<<"Failed"<<endl;
}
return 0;
}