题解 CF1413D Shurikens

简要题意

给定一个 $n$ 和 $2n$ 个操作，第一种操作 “+” 表示从 $1$ ~ $n$ 中选择一个数插入序列，第二种操作 “ - $x$” 表示从当前序列中删除 $x$ 且 $x$ 为当前序列里的最小值，根据给出的操作来推断将数插入序列的合法顺序。

策略分析

不合法情况

不合法的情况有两种。第一种是当在连续取出的两个值中，后取出的值比前取出的值小，因为每次必须取出序列里最小的值，所以这种情况显然是不符合要求的。第二种情况是取出的操作数比放入的操作数多，这样显然也是不合法的。

如何处理合法情况

我们看到这种有进有出的结构能够想到什么，怎么才能反转操作呢？我们很自然地想到可以用栈来实现。我们倒着进行操作，遇到取数操作就把取出来的数压入栈 $s$，遇到插入操作就把 $s$ 栈顶元素弹出来塞进另一个栈 $ans$ 里，最后把 $ans$ 里的元素依次弹出就是答案所要的序列了。按照刚刚讨论过的不合法情况，当 $s$ 中入栈元素比栈顶元素大则不合法，如果需要弹出时栈 $s$ 为空则不合法。

正确性证明

因为每次都要取序列中的最小值，所以后出来的元素一定是更大的，我们就默认它插入得更早。而倒序插入的时候保证了小的元素一定后进栈，所以也不会出现弹出一个数时它还没插入的情况。当 $s$ 入栈元素大于栈顶元素，就相当于操作时取出的值不是最小值；而当弹栈时栈空了，就说明插入的数量少于取出的数量，刚好就对应上了上面分析的不合法情况。由此就可以判断出其正确性。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;

namespace SHAWN {
    stack<int> s;
    stack<int> ans;
    vector<int> opt;// 记录操作
    int n;
    int work()
    {
        cin >> n;
        for (int i = 1; i <= 2 * n; ++i) {
            char op; int x;
            cin >> op;
            if (op == '+') { opt.emplace_back(0); }
            else if(op == '-') { cin >> x; opt.emplace_back(x); }
        }
        for (int i = opt.size() - 1; i >= 0; --i) {
            // 倒着复现操作
            if (!opt[i]) {
                if (s.empty()) { cout << "NO\n"; return 0; }
                // 插入的数量少于取出的数量
                else { ans.push(s.top()); s.pop(); }
            }
            else {
                if (s.size() && opt[i] > s.top()) { cout << "NO\n"; return 0; }
                // 操作时取出的值不是最小值
                else { s.push(opt[i]); }
            }
        }
        cout << "YES\n"; 
        while (!ans.empty()) { cout << ans.top() << ' '; ans.pop(); }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

说些什么吧！

twikoo