Skip to content

S2OJ - 1199. 90 岁的张哥哥

题解约 1.5 千字
检测到 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 尽管是最小的序列,但是是不合法的。正确的做法是先将 5533 压入栈中,弹出 33,压入 22,弹出 22,弹出 55

数据规模与约定

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

思路

70 分

考虑贪心。

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

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

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

100 分

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

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

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

代码

70 分代码
#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 分代码
#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;
}