• 题目：Stack

• 题意：数组b代表单调栈的元素个数, 数组a为栈内的元素(1 <= ai <= n)，有伪代码如下：

Stk is an empty stack
for i = 1 to n :
    while ( Stk is not empty ) and ( Stk's top > a[i] ) : 
        pop Stk
    push a[i]
    b[i]=Stk's size

问是否能得到一个符合条件的数组a序列

• 题解：首先需要构造b数组，若bi没有被指定，则构造

\[b_i = b_{i-1} + 1 \]

因为相邻的两次操作栈内元素不可能相差超过1（要么出栈、要么不出栈），接着分两种情况讨论：

1. 找不到符合条件的序列：
   1. 相邻两次操作栈内元素个数超过1，则找不到符合条件序列
2. 可以找到符合条件的序列
   1. 从序列a的最后一个元素(an)开始构造，判断bi与当前栈内元素的关系, 若大于栈内元素个数，则不断往栈里添加元素，否则将栈顶元素给ai

ps：我是看这个博主的题解学到的构造

• 代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e6 + 5;
int a[N], b[N], st[N];
int n, k;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= k; i++)
    {
        int p, x;
        cin >> p >> x;
        b[p] = x;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!b[i]) b[i] = b[i - 1] + 1; //构造b数组
    }
    for(int i = 0; i < n; i++)
    {
        if(b[i + 1] - b[i] > 1) //相邻的两次操作栈内元素不可能相差超过1
        {
            cout << "-1" << endl;
            return 0;
        }
    }
    int tot = 0; //栈顶（栈内元素个数）
    int cnt = 0; //栈内元素(1、2、3...n依次放入)
    for(int i = n; i >= 1; i--) //模拟栈
    {
        while(b[i] > tot) st[++tot] = ++ cnt; //元素入栈
        a[i] = st[tot--]; //栈顶元素出栈
    }
    for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
    return 0;
}