【练习】新建 Microsoft Office Word 文档

新建 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->n一条龙创建下去。
但如果你删除了前面的文件，而且是多个的话，就从最小的那个，把这些文件命名中的空缺填充完整。
（这里要注意特判删除了本来就没有文件的情况）

算法讲解

既然题目读懂了，算法怎么写？这里主要就是优先队列！那么我们为啥要用优先队列呢？
我在读题中已经读的很明白了：有多个已经被删除的文件，就从最小的那个开始填充。怎么找最小的？优先队列不就超级方便？
所以我们这里就知道了：
在新建的时候，我们先查队列里面有没有元素（表示前面有没有填满），填满了就往后创建（这里用一个变量指着最大创建到的位置），没满就从队列里面取呗。
那在删除的时候，就判断这个能不能删，能删就删了放队列里面呗。

算法操作

我们已经知道了算法，就来讲一下详细操作：
先用一个pos指针指到当前创建的尾部（最大创建值处），再用一个bool类型的word数组当标记数组。
我们就直接模拟：

如果是新建的话：就考虑是新建在删掉的东西上还是新建在尾部。

if ("New" == s)
        if (pq.empty()) {
            cout << pos << endl;
         word[pos++] = 1;
    }
    //前面都被填满时，队列为空
    else {
        int x = pq.top(); pq.pop();
        word[x] = 1;
        cout << x << endl;
    }
    //没被填满取第一个元素

如果是删除的话：除了越界，位置空之外，就直接删除并入队（入队时因为这里空了，要等新建的时候来补）。

else {
    int x; cin >> x;
    //输入删除的数据
    if (x < pos && word[x]) {
        word[x] = 0;
        pq.push(x);
        cout << "Successful" << endl;
    }
    //如果这个数据是存在而且可以删除的
    else cout << "Failed" << endl;
    //如果这个数据不存在或者是已经被删除 
}

打代码

首先我们按要求输入。
然后逐步按照上面模拟就好了。
看我完整代码趴 ~

AC代码

#include <iostream>
#include <bitset>
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7; 
bool word[MAX]; priority_queue<int, vector<int>, greater<int> > pq;
//全局变量区

int main() {
    IOS;
    int T; cin >> T;
    int pos = 1;
    while (T--) {
        string s; cin >> s;
        if ("New" == s)
            if (pq.empty()) {
                cout << pos << endl;
                word[pos++] = 1;
            }
            //前面都被填满时，队列为空
            else {
                int x = pq.top(); pq.pop();
                word[x] = 1;
                cout << x << endl;
            }
            //没被填满取第一个元素
        else {
            int x; cin >> x;
            //输入删除的数据
            if (x < pos && word[x]) {
                word[x] = 0;
                pq.push(x);
                cout << "Successful" << endl;
            }
            //如果这个数据是存在而且可以删除的
            else cout << "Failed" << endl;
            //如果这个数据不存在或者是已经被删除
        }
    }
    return 0;
}
//函数区

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

憨憨的专栏