求助:TLE

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

YunJ @ 2018-08-13 09:11:19

为什么老是TLE

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int minn,maxn,i,n,k,j;
    cin>>n>>k;
    int a[n];
    int maxi[n-k+1];
    int mini[n-k+1];
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<=(n-k+1);i++)
    {
        minn=maxn=a[i];
        for(j=i;j<i+k;j++)
        {
            if(a[j]>maxn) maxn=a[j];
            if(a[j]<minn) minn=a[j];
        }
        maxi[i]=maxn;
        mini[i]=minn;
    }
    for(i=0;i<=n-k;i++)
        cout<<mini[i]<<" ";
    cout<<endl;
    for(i=0;i<=n-k;i++)
        cout<<maxi[i]<<" ";
    cout<<endl;
}

第九、第十和第二都TLE过


by Juanzhang @ 2018-08-13 09:14:35

@yuntianming 您的时间复杂度不对啊


by Juanzhang @ 2018-08-13 09:19:20

@yuntianming 单调队列/线段树/st表 了解一下


by YunJ @ 2018-08-13 09:21:50

@小光 好的,其实这程序很不稳定,有时可以AC 9个有时只能AC 7个


by Juanzhang @ 2018-08-13 09:25:52

@yuntianming 但您的时间复杂度O(n^2)


by YunJ @ 2018-08-13 09:27:49

没想出来O(n)及以下的算法(哭)


by YunJ @ 2018-08-13 09:27:56

@小光


by 蒟蒻lxy @ 2018-08-26 13:26:37

printf


|