题解 P3487 【[POI2009]ARC-Architects】

· · 题解

水题，建议降黄。

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

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

虽然题目有些迷惑写了 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;
}