题目链接：
http://acm.pku.edu.cn/JudgeOnline/problem?id=2823
#include<iostream>
using namespace std;
int n,k;
int a[1000002];
void puts_val(int flag)
{
int q[1000002];
int i,head=0,tail=0;
if(flag)
{
for(i=1;i<=k-1;i++)
{
while(head<tail&&a[q[tail-1]]<a[i]) tail--;
q[tail++]=i;
}
for(i=k;i<=n;i++)
{
while(head<tail&&a[q[tail-1]]<a[i]) tail--;
q[tail++]=i;
while(head<tail&&i-q[head]>=k) head++;
if(i!=n) printf("%d ",a[q[head]]);
else printf("%d\n",a[q[head]]);
}
}
else
{
for(i=1;i<=k-1;i++)
{
while(head<tail&&a[q[tail-1]]>a[i]) tail--;
q[tail++]=i;
}
for(i=k;i<=n;i++)
{
while(head<tail&&a[q[tail-1]]>a[i]) tail--;
q[tail++]=i;
while(head<tail&&i-q[head]>=k) head++;
if(i!=n) printf("%d ",a[q[head]]);
else printf("%d\n",a[q[head]]);
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
puts_val(0);
puts_val(1);
//system("pause");
return 0;
}
posted on 2010-08-24 17:23
wuxu 阅读(211)
评论(0) 编辑 收藏 引用 所属分类:
数据结构