Skip to content

S2OJ - 1199. 90 岁的张哥哥

题解约 1.5 千字
# S2OJ # 线段树 # 模拟 # 栈
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

本题是 洛谷 - P1750 出栈序列 的加强版。

#题面

#题目背景

90 岁的张哥哥躺在床上，奄奄一息，No enemy 和小叶子在两旁伺候。

ck 赶来：「lzl 块状链表调不出来，你去帮他 debug 吧。」
张哥哥：「老了，让这蒟蒻自己去调。」
风雪山神猫的林教头的林妹妹赶来（好像有什么不和谐的东西乱入了）：「后宫『着火了』又！」
张哥哥：「老了，没力气了，我相信你能搞定的。」

这时，张哥哥的手机铃声「星空使者」响起，电话那头是镕昊和克凡：「我们在 ACM 的现场，发现栈不会写……」话音未落，张哥哥腾得一声跳了起来，容光焕发：「什么？！栈都不会写，放着我来！」

这件事情告诉我们，栈，是张哥哥生前最喜欢的数据结构（与事实不符别怪我）。

#题目描述

我们知道，给定一个由 NN 个元素构成的序列，将其中的元素按顺序压入一个大小为 CC 的栈并弹出。元素按它们的出栈顺序进行排列，会得到一个新的序列。这样的序列可能会有很多种，请输出所有新序列中第一个元素最小的序列（若第一个元素最小的序列有多个，则令第二个尽可能小；若仍有多个，则令第三个最小，以此类推）。

#输入格式

第一行两个正整数 N,CN, C。

第二行 NN 个整数，表示将顺序入栈的元素的值。

#输出格式

仅一行，即满足要求的序列。

#输入输出样例

样例输入 #1

3 2
5 3 2

样例输出 #1

3 2 5

样例说明 #1

因为栈的大小为 22，所以 2 3 5 尽管是最小的序列，但是是不合法的。正确的做法是先将 55、33 压入栈中，弹出 33，压入 22，弹出 22，弹出 55

#数据规模与约定

  • 对于 40%40\% 的数据，n≤12n \leq 12；
  • 对于 70%70\% 的数据，n≤10000n \leq 10000；
  • 对于 100%100\% 的数据，c≤n≤300000c \leq n \leq 300000，元素大小均在 2×1092 \times 10^9 以内。

#思路

#70 分

考虑贪心。

设定两个指针 l,rl, r，初始值为 11 和 CC。

循环 nn 次，每次找出 [l,r][l, r] 区间中未被标记的最小的数并输出、标记，然后将 ll 跳到前一个未被标记的数，rr 增加 11。

可以证明这个贪心是正确的。

#100 分

使用线段树维护区间最小值可以将区间最值的查询从 O(n)O(n) 降至 O(log⁡n)O(\log n)。

使用栈模拟实际操作可以省去标记已入栈的数，需要遵循以下几点注意事项：

  1. 入栈时需要将当前区间内的最小值前的所有未入栈元素入栈。
  2. 确保栈内元素数量不超过栈容量。
  3. 弹出栈顶元素后从栈顶元素的后一个元素开始执行上述过程。

#代码

70 分代码
C++
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
#include <algorithm>
#include <iostream>
#include <limits>

using std::cin;
using std::cout;
using std::endl;

const int N = 300005;

int n, c, l, r, a[N];
bool vis[N];

int main() {
    std::ios::sync_with_stdio(false);
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    l = 1, r = c;
    for (int i = 1; i <= n; i++) {
        int p = std::min_element(a + l, a + r + 1) - a;
        cout << a[p] << ' ';
        vis[p] = true;
        a[p] = std::numeric_limits<int>::max();
        while (p && vis[p]) p--;
        l = std::max(p, 1);
        r = std::min(r + 1, n);
    }
    cout << endl;
    return 0;
}
100 分代码
C++
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <limits>
#include <stack>

using std::cin;
using std::cout;
using std::endl;

// Limits
const int N = 300005;

// Variables
int a[N];
bool vis[N];

// Segment Tree
void build(int, int, int);
int query(int, int, int);

int main() {
    std::ios::sync_with_stdio(false);

    int n, c;
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    a[0] = std::numeric_limits<int>::max();
    build(1, 1, n);

    int pos = query(1, 1, c);
    std::stack<int> st;

    for (int i = 1; i < pos; i++) {
        st.push(i);
    }
    cout << a[pos] << ' ';

    for (int i = c + 1; i <= n; i++) {
        int p = query(1, pos + 1, i);
        if (!st.empty() && a[st.top()] <= a[p]) {
            cout << a[st.top()] << ' ';
            st.pop();
        } else {
            for (int j = pos + 1; j < p; j++) {
                st.push(j);
            }
            pos = p;
            cout << a[p] << ' ';
        }
    }

    for (int i = 1; i < c; i++) {
        int p = pos + 1 <= n ? query(1, pos + 1, n) : 0;
        if (!st.empty() && a[st.top()] <= a[p]) {
            cout << a[st.top()] << ' ';
            st.pop();
        } else {
            for (int j = pos + 1; j < p; j++) {
                st.push(j);
            }
            pos = p;
            cout << a[p] << ' ';
        }
    }

    cout << endl;

    return 0;
}

// === Segment Tree ===

struct node {
    int l, r, id;

    node()
        : l(0), r(0), id(0) {}
    node(int _l, int _r)
        : l(_l), r(_r), id(0) {}
} tr[N << 2];

inline void pushup(int u) {
    tr[u].id = a[tr[u << 1].id] <= a[tr[u << 1 | 1].id] ? tr[u << 1].id : tr[u << 1 | 1].id;
}

void build(int u, int l, int r) {
    tr[u] = node(l, r);
    if (l == r) {
        tr[u].id = l;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

/**
 * 查询区间 [l, r] 最小值，并返回最小值在 a 数组中对应的**下标**
 * @param u 根节点坐标
 * @param l 区间左端点
 * @param r 区间右端点
 * @return 最小值在 a 数组中对应的**下标**
 */
int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].id;
    int mid = tr[u].l + tr[u].r >> 1,
        pos = 0;
    if (l <= mid) {
        int t = query(u << 1, l, r);
        if (a[t] < a[pos]) pos = t;
    }
    if (r > mid) {
        int t = query(u << 1 | 1, l, r);
        if (a[t] < a[pos]) pos = t;
    }
    return pos;
}