Nibelungen @ 2017-08-28 20:50:17
line 1 column 1,read -645 ,expected 780 -
#include<cstdio>
#include<cstring>
using namespace std;
#define m 1000000007
int n,k,que[10000010],nu[10000010],head,tail;
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&nu[i]);
if(n==1){
printf("%d\n%d",nu[0],nu[0]);
}
que[tail++]=head;
for(int i=1;i<n;i++){
if(nu[i]>nu[que[tail-1]]) que[tail++]=i;//如果大于队尾就入队,成升列
else{ //如果小于或者等于,那就要去掉比他大的
if(nu[que[head]]>nu[i]) head=tail;
else{ //第二种情况要插在中间
while(nu[que[tail-1]]>nu[i]) que[tail--]=0;
}
que[tail++]=i;
}
while(i-que[head]>=k) head++; //如果已经出了窗口
if(i>=k-1) printf("%d ",nu[que[head]]);
}
memset(que,0,sizeof(que));
printf("\n");
//复制一遍
for(int i=1;i<n;i++){
if(nu[i]<nu[que[tail-1]]) que[tail++]=i;
else{
if(nu[que[head]]<nu[i]) head=tail;
else
while(nu[que[tail-1]]<nu[i]) que[tail--]=0;
que[tail++]=i;
}
while(i-que[head]>=k) head++;
if(i>=k-1) printf("%d ",nu[que[head]]);
}
}
by ars4me @ 2017-09-04 08:16:42
head和tail?
by 梨马羊 @ 2017-09-22 18:16:01
k=1时过不去
by 梨马羊 @ 2017-09-23 07:57:34
@ Nibelungen
by 梨马羊 @ 2017-09-25 10:15:17
@Nibelungen
by Nibelungen @ 2017-10-03 17:13:33
@梨马羊 好的谢谢