Stack

题目大意

有n个数，依次加进栈中，每次加入前将栈顶比大的所有元素弹掉，加入后记为栈的大小

现在给你b中的一些数，让你求a数组的一种合法方案，其中1~n在a中各出现了一次

解题思路

每次把栈顶比大的所有元素弹掉，使得栈是单调递增的

对于所求a数组，可以先连边，表示该点要比哪个点大，然后跑拓扑序

那么可以遍历每个b，如果当前栈中剩余的数大于了个，那么把这些数弹掉，且弹掉的数中最小的数连向i（这些数要比大才能被弹掉），把i加进栈中，然后连向栈顶（栈顶不会被弹掉）

最后跑拓扑序编号

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1000100
using namespace std;
int n, m, x, w, p, g, res, st[N], v[N], b[N], to[N], deg[N];
queue<int>d;
void bfs()
{
    for (int i = 1; i <= n; ++i)
        if (!deg[i]) d.push(i);
    w = n;
    while(!d.empty())
    {
        int u = d.front();
        d.pop();
        v[u] = w--;
        if (!--deg[to[u]]) d.push(to[u]);
    }
    return;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d", &x);
        scanf("%d", &b[x]);
    }
    res = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (b[i])
        {
            if (b[i] > res + 1)//所要求的比当前剩余的大，所以不可能
            {
                p = 1;
                break;
            }
            g = 0;
            while(b[i] < res + 1)//多了
                res--, g = 1;
            if (g) to[st[res + 1]] = i;//最低的点比大
        }
        st[++res] = i; //入栈
        to[st[res]] = st[res - 1];//i比栈顶大
    }
    if (p == 1)
    {
        puts("-1");
        return 0;
    }
    for (int i = 1; i <= n; ++i)
        deg[to[i]]++;
    bfs();//跑拓扑序
    for (int i = 1; i <= n; ++i)
        printf("%d ", v[i]);
    return 0;
}