P1750 出栈序列(滑动窗口加贪心)

P1750 出栈序列(滑动窗口加贪心)

2019年11月11日 1 作者 Ender

题面

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

输入格式

第一行,两个数n,c

第二行n个数,为序列中n个元素的值

输出格式

输出n个数,为满足要求的序列。

样例输入

6 3
5 2 3 8 7 4

样例输出

2 3 5 4 7 8

思路讲解

这题是显然的滑动窗口,我们创建一个大小为c的滑动窗口,用两个变量来存储区间最小值和最小值指针:min_ans, ans_dot。需要注意的是,我们还需要开一个辅助栈x,如果a[r]不是区间最小值,即后面有更大的数字,需要将a[r]压入栈中。每次获得区间最小值后,都要对栈顶元素进行比较,如果栈顶元素更小,弹出栈顶元素并存入答案序列,若区间最小值更小,则将区间最小值存入答案序列。滑动窗口完成后需要对x进行监测是否为空,若不为空则出栈所有元素并存入答案序列。最后输出答案序列ans即可。

AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

#define int long long
int n, c;
int a[23333];
int min_ans;
int ans[23333];
int l = 1, r = 1;
int ans_dot, min_dot;
std::stack<int> x;

signed main() {
    std::cin >> n >> c;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    min_ans = 2 * 0x3f3f3f3f;
    while (r <= n) {
        for (; r - l + 1 + x.size() <= c && r <= n; r++) {
            //std::cout << l << ' ' << r << ' ' << x.size() << std::endl;
            if (min_ans >= a[r]) {
                min_ans = a[r];
                min_dot = r;
            }
        }
        if (x.size() != 0 && x.top() <= min_ans) {
            //std::cout << 1 << std::endl;
            ans[++ans_dot] = x.top();
            x.pop();
            min_ans = 2 * 0x3f3f3f3f;
            r = l;
        } else {
            //std::cout << 2 << std::endl;
            for (; l < min_dot; l++) {
                x.push(a[l]);
            }
            l = min_dot + 1;
            r = min_dot + 1;
            ans[++ans_dot] = min_ans;
            min_ans = 2 * 0x3f3f3f3f;
        }

    }
    if(ans_dot < n) {
        while (x.size() != 0) {
            ans[++ans_dot] = x.top();
            x.pop();
        }
    }
    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << " ";
    }
    return 0;
}