P1750 出栈序列（滑动窗口加贪心）
题面
给定一个由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;
}
Orz Ender