DDOSvoid's Blog

2021牛客多校2 K Stack

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11253/K

简要题解：给定长度 $n$​ 和若干个前缀的单调栈的大小，要求构造一个满足条件的排列

$n\le 10^6$

Solution

首先对于没有给定单调栈大小的位置，我们一定是添加元素

对于给定的位置，如果大小不够就无解，否则我们就直接一直弹出

在过程中跑一个拓扑关系即可

时间复杂度 $O(n)$

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <stack>
#include <queue>
#define maxn 1000010
using namespace std;

int n, m, a[maxn];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn], in[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; ++in[v];
    e[c1].next = head[u]; head[u] = c1++;
}

int id[maxn], cnt;
void topsort() {
    queue<int> Q;
    for (int i = 1; i <= n; ++i)
        if (!in[i]) Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        id[u] = ++cnt;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (--in[v] == 0) Q.push(v);
        }
    }
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        a[x] = y; 
    } stack<int> S;
    for (int i = 1; i <= n; ++i) {
        if (!a[i]) {
            if (!S.empty()) add_edge(S.top(), i);
            S.push(i);
        } else {
            if (S.size() + 1 < a[i]) return cout << -1 << "\n", 0;
            while (S.size() + 1 > a[i]) {
                add_edge(i, S.top());
                S.pop();
            }
            if (!S.empty()) add_edge(S.top(), i);
            S.push(i);
        }
    } topsort();
    for (int i = 1; i <= n; ++i) cout << id[i] << " \n"[i == n];
    return 0;
}