题解：P3487 [POI 2009] ARC-Architects

题意

给出一个序列

a_n

，在这个序列中选出一个长度为

k

的子序列，使得这序列的字典序最大。

分析

很容易想到，如果想要字典序尽可能的大，就要让每次选的数最大，但是为了让子序列的长度为

k

，在选第

i

个数时，后面至少要留

k-i

个数，也就是说，第

i

个数的选择范围是

[p,n-k+i]

，其中

p

是选择的上一个数的位置，因此我们可以考虑用单调队列去维护。

AC code

CPP

#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;
}

题解：P3487 [POI 2009] ARC-Architects

文章操作

题意

分析

AC code

相关推荐

评论

题解：P3487 [POI 2009] ARC-Architects