90分求助!!

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

hulean @ 2018-07-31 16:52:42

谁帮我看一下哪有问题

我只有90分,一个测试点TLE了

  • 多谢
  • 代码如下:
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int a[1000100],js[1000100];
int read()
{
    int tot=0,f=1;char c=getchar();  
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }  
    while(c>='0'&&c<='9')
    {
        tot=(tot*10)+c-'0';
        c=getchar();
    }
    return tot*f;
}
int main()
{
    register int n,l,r,k,minn,maxn;
    n=read();k=read();
    for(register int i=1;i<=n;i++)a[i]=read();
    l=1;r=k;
    while(r<=n)
    {
        maxn=-INF;
        minn=INF;
        for(register int i=l;i<=r;i++)
        {
            maxn=max(maxn,a[i]);
            minn=min(minn,a[i]);
        }
        printf("%d ",minn);
        js[l]=maxn;
        l++;r++;
    }
    cout<<endl;
    for(register int i=1;i<l;i++)
    {
        printf("%d ",js[i]);
    }
    return 0;
}

by 斗神·君莫笑 @ 2018-07-31 16:57:05

@huleanhulean 等等,还有rigister不是循环不要开,不然更慢


by FakeZGR @ 2018-07-31 16:58:11

inline int read() 会快一点


by 斗神·君莫笑 @ 2018-07-31 16:58:14

@huleanhulean 我怎么觉得你是暴力呢?


by 斗神·君莫笑 @ 2018-07-31 16:59:54

@huleanhulean 请使用队列优化


by Marser @ 2018-07-31 17:17:06

@huleanhulean 你这样写还能过9个点真是难得。


by hulean @ 2018-08-01 08:11:29

@斗神·君莫笑 队列优化是什么


|