下不了数据,九十分求助

P1886 滑动窗口 /【模板】单调队列

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

@梨马羊 好的谢谢


|