题解：P3487 [POI 2009] ARC-Architects

Istruggle · 2025-06-10 11:15:07 · 题解

题意

给出一个序列 a_n，在这个序列中选出一个长度为 k 的子序列，使得这序列的字典序最大。

分析

很容易想到，如果想要字典序尽可能的大，就要让每次选的数最大，但是为了让子序列的长度为 k，在选第 i 个数时，后面至少要留 k-i 个数，也就是说，第 i 个数的选择范围是 [p,n-k+i]，其中 p 是选择的上一个数的位置，因此我们可以考虑用单调队列去维护。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,k,a[15000005],q[15000005];
int main(){
    k=inicjuj(); a[1]=wczytaj(); n=1;
    while(a[n]!=0) a[++n]=wczytaj(); n--;
    int h=1,t=0,pos=1;
    for(int i = 1;i<=n;i++){
        while(h<=t&&q[t]<a[i]) t--;
        q[++t]=a[i];
        if(i==n-k+pos){
            wypisz(q[h]); h++;
            pos++;
        }
    }
    return 0;
}