自动搬运

查看原文

来自洛谷，原作者为

	FZzzz **

搬运于2025-08-24 21:28:39，当前版本为作者最后更新于2019-06-16 15:26:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

原题解锅了，这里整个重写一遍。

以下内容写于 2022 年 8 月 5 日。

论还有半个月就退役的我在这里水黄题。

---

三年前还是普及组选手的我做过这题，当时看不懂题解，自己整了个线性做法，然而没有正确性证明。

三年后这篇题解成为了我赞最多的博客，然而我发现它锅了。并且我毫不意外地还是看不懂其他题解。

现在我们来修这个锅。

---

下面令 $m$ 表示题面里的 $c$。

我们有两种操作：入栈和出栈。入栈这个操作会对栈产生影响，但不会对结果序列产生影响，这很不利于我们的分析。

我们希望每一步都能使结果序列后面多一个数，那么我们把两种操作改成：

• 出栈一个数。
• 连续入栈至少一个数，然后出栈一个数。

这和原来的两种操作是等价的。

执行第二种操作时，我们要入栈多少个数呢？由于我们要最小化的的是字典序，所以我们肯定贪心地想要让入栈的最后一个数，即出栈的那个数最小。

令 $l$ 为 $a$ 中第一个还没有被入栈的数的位置，$r$ 表示我们最多可以一次性入栈 $r-l+1$ 个数，也就是说最多可以把下标在 $[l,r]$ 中的所有数都入栈。如果当前栈中有 $s$ 个元素，我们可以算出 $r=\min\{l+m-s-1,n\}$。

那么，如果我们这一步入栈 $x-l+1$ 个数，再出栈一个数即 $a_x$，我们想要 $a_x$ 是 $a_l$ 到 $a_r$ 中最小的数。这样我们就可以知道，这一步如果执行第二种操作，需要连续入栈多少个数了。

比较严谨的小朋友就要问了，最小的 $a_x$ 可能不止一个呀？等会我们再讨论这个问题。

但是，有两种操作，我们应该执行哪一个呢？不难发现，我们应该比较 $a_x$ 和当前的栈顶元素。如果 $a_x$ 更小，则执行第二种操作，否则执行第一种操作。

严谨的小朋友又要问了，如果两个数相等呢？我们还是等会再来讨论这个问题。

---

可能光说比较难以理解，我们来手玩一下样例：

6 3
5 2 3 8 7 4

1. 当前栈为空，$l=1$，$r=3$，$x=2$。执行第二种操作，入栈两个数再出栈一个数即 $a_x=2$。
2. 当前栈为 $[5]$，$l=3$，$r=4$，$x=3$。由于 $a_x=3$ 小于栈顶 $5$，执行第二种操作，入栈一个数再出栈一个数 $3$。
3. 当前栈为 $[5]$，$l=4$，$r=5$，$x=5$。由于 $a_x=7$ 大于栈顶 $5$，执行第一种操作，出栈一个数 $5$。
4. 当前栈为空，$l=4$，$r=6$，$x=6$。执行第二种操作，入栈三个数再出栈一个数 $4$。
5. 当前栈为 $[8,7]$（右边是栈顶），$l=7$（用 $l>n$ 表示原序列中没有数没有被入栈了），$r=6$。执行第一种操作，出栈一个数 $7$。
6. 当前栈为 $[8]$，执行第一种操作，出栈一个数 $8$。

最终得到的结果序列是 $[2,3,5,4,7,8]$，跟样例输出是一样的。

---

如果没有相同的元素，问题就已经被解决了。真可惜，我们还得回过头来讨论上面提出的两种相等的情况。

如果最小元素不止一个？

猜测一下，我们选择最左边的那个。但是为什么呢？

考虑利用反证法证明这个结论：假设有两个数 $x$ 和 $y$ 满足 $l\le x<y\le r$，$a_x=a_y$，我们假设选 $y$ 可以得到更优的结果。那么，我们开辟一条新的世界线，考虑在这个世界线里选择 $x$ 并进行一次操作二。

接着，我们把下标 $[x+1,y]$ 的数全部入栈（不出栈）。这样，我们的情况相比于原世界线执行完这次操作二之后的情况，只是栈里的 $a_x$ 跨越了一些不小于它的数跑到了栈顶。

这种情况显然是不劣于原世界线的。因为，我们之后可以对原世界线的每一次操作，都在新世界线里执行一样的操作。容易证明结果序列不劣于原来的世界线。

于是我们导出了假设的矛盾！根据反证法，我们可以证明结论，即我们应该选择左边的 $x$ 而非右边的 $y$。

如果 $a_x$ 等于栈顶元素？

那么我们断言直接进行出栈操作是不劣的。证明和上面几乎一样，留给读者作练习。

下面的话留给普及组选手：

如果你不会证明，你可以手玩一些数据来猜测并验证结论。比如下面两个数据就对应了上面两种情况。

3 3
1 2 1

4 3
2 1 3 2 

但是！不要觉得这样证明就没有用了。你可能听说过“OIer 不需要证明”的说法，但是这种想法是绝对错误的。

不是所有结论都可以手玩或者感性理解，凭借直觉去猜结论经常会猜错。所以一定要养成多问证明的好习惯，即使在考场上你可能不会严谨证明每个结论。

……好吧，其实我是一个直觉很差的选手，而且每个结论我都需要一个严谨到每个字的证明。这对我平时做题和考试都造成了不小的负面影响。所以可能我是错的，我这种傻逼的建议听听就好。

---

等等！我们怎么找到这个 $x$ 呢？当然可以暴力或者使用 std::multiset 进行优化，得到 $O(n^2)$ 或者 $O(n\log n)$ 的时间复杂度并通过此题。但是，不是说有线性做法吗？

可以证明，$l$ 和 $r$ 都是单调不减的。这样左右端点都只会往一个方向移动的区间，我们称之为滑动窗口。我们要做的就是维护这个窗口内最靠左的最小值。

我们使用单调队列线性解决这个问题。这里有一道模板题，也可以去看看这题的题解。如果你已经会了这个数据结构，你可以跳过这一段。

单调队列基于这样一个事实：如果有两个位置 $x$ 和 $y$，满足 $x<y$ 且 $a_x>a_y$，那 $a_x$ 就永远没用了。因为 $a_y$ 会更晚从窗口里被移出去，而且还更小。

我们用一个双端队列维护窗口内所有有用的数，队列里从队头到队尾下标递增，那么值是不降的。每次我们要移动窗口的左端点时，就把队头的一些元素出队。

而我们要移动右端点时，就入队一些元素。每次入队会使队尾的一些元素变得没用，要在入队之前把它们从队列里移出去。

这样，队头就是当前窗口内最靠左的最小值。那么这个做法的时间复杂度是多少呢？每个元素只会入队一次，出队一次，所以是 $O(n)$ 的。

那么我们在线性时间内完整解决了整个问题。由于输入就需要这么多时间，我们做到了理论最优的时间复杂度。

这里把单调队列讲一遍纯粹是因为原来写的题解讲了一遍。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline ll read(){
	ll x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') f=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=1e4+5;
int n,m,a[maxn],q[maxn],hd=1,tl=0;
int main(){
#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	n=read();
	m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++){
		while(hd<=tl&&a[i]<a[q[tl]]) tl--;
		// 必须是 a[i]<a[q[tl]] 而不是 <=
		q[++tl]=i;
	}// 入队最开始 m 个元素
	int l=1,r=m;
	vector<int> s;// 栈
	for(int i=1;i<=n;i++){
		if(hd<=tl&&(!s.size()||a[q[hd]]<s.back()))
		// 比较两种操作，必须是 < 而不是 <=
			while(l<=q[hd]) s.push_back(a[l++]);
		// 入栈一堆元素
		printf("%d ",s.back());
		s.pop_back();// 出栈并输出
		while(r<n&&r<l+m-(int)s.size()-1){// 移动 r
			r++;
			while(hd<=tl&&a[r]<a[q[tl]]) tl--;
			q[++tl]=r;// 入队
		}
		while(hd<=tl&&q[hd]<l) hd++;// 移动 l，出队
	}
#ifdef LOCAL
	fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
	return 0;
}

以下是碎碎念。

事情是这样的。这篇题解被 hack 了，我发现好像在有相等元素时会寄。想了一下修好了，但是不太可能直接在原有题解上修，于是决定重写。

很久没有写黄题的题解了，我也不知道普及组选手喜欢什么样的。太简略的题解肯定是看不懂的，但是我当时好像也嫌弃一些题解总是啰里吧嗦讲一大堆有的没的。但是没办法，只能按怎么详细怎么来了。

这应该是我博客里现有的最早的文章，也是赞最多的一篇。我会认真对待它，希望对你有帮助。

莫名其妙写了这么长，比我很多黑题的题解都长多了。就到这里吧。