蒟蒻求助,ST表RE了!!!60分,其他RE

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

hyfhaha @ 2018-08-02 08:59:28

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int fmax_[310101][33],fmin_[310101][33],s,n,m,p,x,y;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {   
        scanf("%d",&s);
        fmax_[i][0]=s;
        fmin_[i][0]=s;
    }
    //O(nlogn)预处理    DP、倍增思想 
    for(int j=1;j<=(int)(log2(n));j++)                          //j表示区间长度为2^j 
    {
        for(int i=1;i<=n-(1<<j)+1;i++)                          //i表示区间开始点                      
        {
            fmax_[i][j]=max(fmax_[i][j-1],fmax_[i+(1<<(j-1))][j-1]);        //转移方程f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
            fmin_[i][j]=min(fmin_[i][j-1],fmin_[i+(1<<(j-1))][j-1]);        //转移方程f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
        }
    }
    //O(1)查询
    for(int i=1;i<=n-m+1;i++) 
    {
        x=i;y=i+m-1;
        if(y-x+1<=0)
        p=0;
        else
        p=(int)(log2(y-x+1));
        printf("%d ",min(fmin_[x][p],fmin_[y-(1<<p)+1][p]));
    }
    printf("\n");
    for(int i=1;i<=n-m+1;i++) 
    {
        x=i;y=i+m-1;
        if(y-x+1<=0)
        p=0;
        else
        p=(int)(log2(y-x+1));
        printf("%d ",max(fmax_[x][p],fmax_[y-(1<<p)+1][p]));
    }
    return 0;
}

敢问为什么RE??? 60分


by CreeperK @ 2018-08-08 10:00:06

还有就是本题可以只用两个一维数组(因为长度是固定的)


上一页 |