是谁贴上了倍增的标签,果断TLE2点啊==

P1440 求m区间内的最小值

睿屿青衫 @ 2017-10-17 20:22:54

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 3000000
using namespace std;
int n,m,minn[maxn][24];
void init()
{
    for(int j=1;(1<<j)<=n;++j)
     for(int i=1;i+(1<<j)-1<=n;++i)
      minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
}
int rmq_min(int l,int r)
{
    int k=log2(r-l+1);
    return min(minn[l][k],minn[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
     cin>>minn[i][0];
    init();
    for(int i=1;i<=n;++i)
     {
         if(i==1) printf("0\n");
          else if(i<=m) printf("%d\n",rmq_min(1,i-1));
           else printf("%d\n",rmq_min(i-m,i-1));
     }
    return 0;
}
80不嫌弃拿走

by 青衫白叙 @ 2017-10-30 11:00:58

@xw001 fread 的那个?。。我还有别的。。


by 青衫白叙 @ 2017-10-30 11:10:33

@xw001 这题卡的RMQ 的空间吧。。。fread 也要空间。。所以不能用fread啊。。


by xw001 @ 2017-10-30 11:11:42

@青衫白叙 。。。。


by 青衫白叙 @ 2017-10-30 11:12:43

@青衫白叙 而且你也没用fread 啊。。。


上一页 |