自动搬运

查看原文

来自洛谷，原作者为

	a___ 这个家伙很蒻，什么也没有留下qwq

搬运于2025-08-24 21:49:28，当前版本为作者最后更新于2020-08-19 14:31:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

水题，建议降黄。

如果交互库下不下来的可以选择直接复制我的模板。

其实就是单调队列模板题，之前两个题解一个堪称史上最短题解，另一个说了半天废话最后放了一堆要么过不了要么太繁琐的代码，于是我就来水题解了。

虽然题目有些迷惑写了 $1\leq b_1\leq b_2\leq \ldots\leq b_k$，但实际是指 $1\leq b_1\lt b_2\lt \ldots\lt b_k$，也就是说同一个数并不能选多次。于是正确的题意为在序列 $a$ 中选一个长度为 $k$ 的子序列使其字典序最大。

具体思路很简单，因为字典序是从前向后比较，所以我们要让前面的数尽可能大，所以我们每次选一个最大值输出；因为后选的不能在前选的前面以及总共只有 $n$ 个数，所以有 $b_1\in[1,n-k+1],b_2\in[b_1+1,n-k+2],\dots,b_k\in[b_{k-1}+1,n]$。

想要解决这个问题，我们可以维护一个单调递减的单调队列，在维护到第 $n-k+i$ 个数的时候取一次最大值并删除，就得到第 $i$ 个位置的值。由于是单调队列，后面取的一定在前面取的值的后面（因为前面的已被顶掉）；仅算到 $n-k+i$ 个数是为了让后面留出至少 $i-1$ 个数的位置；至于每次删掉最值是为了让后面不重复取。

然后我们惊奇地发现，开 一个 int 大小为 $1.5e7$ 的数组竟然不会炸 125MB。于是我们可以先把所有数读进来，这样就可以知道 $n$ 是多少了。由于我们只有在最后 $k$ 位需要从前面弹数，而且我们最多只需要前 $k$ 大的数，所以队列开到 $2e6$ 就好了。

实现上还有一个问题就是平时单调队列需要把相等数全部弹出，但我们这里要把相等的数留下来，因为我们可以取不在同一位置上的相等的数。

最后说一下交互，注意按 评测方式 中说的来，注意不要与交互库重变量名。

c 代码（因为交互库是.c，所以我就写成c了）

/*前180行是交互库，这里省略*/
#define MAXN 15000010
#define MAXM 2000010
int q[MAXM],s,t;
int a[MAXN];
int main()
{
	int k=inicjuj();
	int i;
	do a[++a[0]]=wczytaj(); while(a[a[0]]);
	--a[0];int x=a[0]-k+1;s=0;t=1;
	for(i=1;i<=a[0];i++)
	{
		while(s<=t&&q[t]<a[i])--t;/*不要写=，保留相等数*/
		if(t-s+1<k)q[++t]=a[i];/*保持在k个数之内*/
		if(i>=x)wypisz(q[s]),++s;/*取出最大值*/
	}
	return 0;
}