ST表求助,MLE*2

P1440 求m区间内的最小值

紫妹只有17岁 @ 2018-09-01 20:14:47

求dalao帮一下新学ST表然后MLE*2

世界真不友好

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
const int N=2000001;
const int LogN=21;
int n,m;
int a[N],f[N][LogN+5],LOG[LogN+5];
void slove()
{
    int k=log(n)/log(2)+1;
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n-LOG[j-1];i++)
            f[i][j]=min(f[i][j-1],f[i+LOG[j-1]][j-1]);
    return ;
}
int find(int l,int r)
{
    int k=log(r-l+1)/log(2);
    return min(f[l][k],f[r-LOG[k]+1][k]);
}
int main()
{
    scanf("%d%d",&n,&m);
    LOG[0]=1;
    for(int i=1;i<=LogN;i++)
    LOG[i]=LOG[i-1]<<1;
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),f[i][0]=a[i];
    slove();
    int s=1;
    cout<<0<<endl;
    while(s<=m)
    {
        printf("%d\n",find(1,s));
        s++;
    }
    for(int i=m+1;i<=n-1;i++)
    {
        printf("%d\n",find(i-m+1,i));
    }
    return 0;
}

by UKE自动稽 @ 2018-09-01 20:16:39

@紫妹只有17岁 滚动数组


by 紫妹只有17岁 @ 2018-09-01 20:18:03

@UKE自动机

???dalao什么是滚动数组


by zhaotiensn @ 2018-09-01 20:20:00

@UKE自动机

确定st表真的能滚存吗?一脸懵逼

蒟蒻不会,求大佬讲解。


by x_angelkawaii_x @ 2018-09-01 20:21:41

@紫妹只有17岁
你这个属于算法本身的问题,没救的。。。 试着把st第一维开到22,int改成short吧


by 良月澪二 @ 2018-09-01 20:22:51

ST表这个题过不了 或者说我写不过


by 紫妹只有17岁 @ 2018-09-01 20:25:02

@沉迷学习的YSJ

好像不行呢喵~


by 紫妹只有17岁 @ 2018-09-01 20:25:29

@LinkedIn

好吧我也写不过,那这题用什么算法写比较简单a~


by 夢·壹生所愛 @ 2018-09-01 20:26:09

为毛线不用单调队列做啊


by YWHS__LH @ 2018-09-01 20:27:54

哇大佬们好优秀啊


by YWHS__LH @ 2018-09-01 20:28:45

ST好像是过不了啊


| 下一页