c语言,8,9测试集超时求助!!!!!!

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

UNIQUEx @ 2021-08-26 15:15:20

#include <stdio.h>
#include <stdlib.h>
int max(int);
int min(int);
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int a[10000100],b[10000100],c[10000100];
int top,topnum,k;

int main(int argc, char *argv[]) 
{
    int n;//n表示一共有多少个数字,k代表一次性可以扫描多少个数
    int i,j;
    scanf("%d",&n);
    scanf("%d",&k); 
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    topnum=min(1);
    b[1]=topnum;
    top=1; 
    int t=1;
    int tnum=max(1);
    c[1]=tnum;
    for(i=2;i<=n-k+1;i++)
      {
        if(top<i)
          {
            topnum=min(i);
            b[i]=topnum;
            }
        else
          {
            if(a[top]>a[i+k-1])
              {
                top=i+k-1;
                topnum=a[i+k-1];
                b[i]=a[i+k-1];
                }
            else
              {
                b[i]=topnum;
                  }   
              } 
        if(t<i)
          {
            tnum=max(i);
            c[i]=tnum;
            }
        else
          {
            if(a[t]>a[i+k-1])
              {
                t=i+k-1;
                tnum=a[i+k-1];
                c[i]=a[i+k-1];
                }
            else
              {
                c[i]=tnum;
                  }   
              }       
      }
    for(i=1;i<=n-k+1;i++)
      {
        printf("%d ",b[i]);
        } 
    printf("\n");
    for(i=1;i<=n-k+1;i++)
      {
        printf("%d ",c[i]);
        }       
    return 0;
}
int max(int c)
{
    int i,temp=-2147483647;
    for(i=c;i<c+k;i++)
      {
        temp=temp>a[i]?temp:a[i];
      }
    return temp;  
}
int min(int c)
{
    int i,temp=2147483647;
    for(i=c;i<c+k;i++)
      {
        temp=temp<a[i]?temp:a[i];
      }
    return temp;  
}

by Moeebius @ 2021-08-26 15:22:39

这道题需要用单调队列……


|