문제풀이: 슬라이딩 창【단조로운 대기열】

13234 단어 문제풀이DP
  • N 2 N^2 N2 폭력은 다 할 것 같아
  • N l o g N NlogN NlogN 세그먼트 트리, 트리 배열 ST표 마음대로 하기
  • N N N 단일 큐
    • #include 
#include 
using namespace std;

#define ll long long
#define re register
#define gc getchar()
inline int read()
{
	re int x(0),f(1);re char ch(gc);
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=gc;}
	while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
	return x*f;
}

const int N=1e6+5;
int n,k,a[N],q[N],num[N],f1[N],f2[N],head,tail;

void get_max()
{
	head=1,tail=0;
	for(int i=1;i<=n;++i)
	{
		while(num[head]<i-k+1&&head<=tail) ++head;
		while(a[i]<=q[tail]&&head<=tail) --tail;
		num[++tail]=i,q[tail]=a[i];
		f1[i]=q[head];
	}
	for(int i=k;i<=n;++i)
		cout<<f1[i]<<" ";
	cout<<endl;
}
void get_min()
{
	head=0,tail=1;
	for(int i=1;i<=n;++i)
	{
		while(num[head]<i-k+1&&head<=tail) ++head;
		while(a[i]>=q[tail]&&head<=tail) --tail;
		num[++tail]=i;q[tail]=a[i];
		f2[i]=q[head];
	}
	for(int i=k;i<=n;++i)
		cout<<f2[i]<<" ";
}

int main()
{
	n=read(),k=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	get_max();
	get_min();
	return 0;
}
    Satan Clause is Coming to Town
    [Swift] Rails와 Pusher를 이용해 채팅 아이폰 앱을 제작합니다.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage