为什么会有两个MLE

P1440 求m区间内的最小值

William_Takazaki @ 2023-05-13 19:36:34

啊啊啊啊啊

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10,L=20;
int n,m,a[N],f[N][L],lg[N];
int main(){
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>a[i];
    lg[1]=0;
    for(i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(j=0;j<L;j++){
        for(i=1;i+(1<<j)-1<=n;i++){
            if(j==0)f[i][j]=a[i];
            else f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }for(i=1;i<=n;i++){
        int x,y,k;
        if(i==1)cout<<"0\n";
        else{
            if(i<=m){
                x=1;
                y=i-1;
            }else{
                x=i-m;
                y=i-1;
            }k=lg[y-x+1];
            cout<<min(f[x][k],f[y-(1<<k)+1][k])<<endl;  
        }
    }
    return 0;
}

by Leonid @ 2023-05-13 19:38:43

f[N][L] 已经占了约 150MB。


by William_Takazaki @ 2023-05-13 19:39:39

哎呀,那咋整


by Leonid @ 2023-05-13 19:44:13

@6371 可以考虑使用其他算法,例如单调队列。


by William_Takazaki @ 2023-05-13 19:45:51

@h0494 az,我过来本来就是来练RMQ的。。

你干嘛啊哎嗨哟


by Leonid @ 2023-05-13 19:49:03

@6371 有没有可能,这题卡 st 表。


by William_Takazaki @ 2023-05-13 19:50:18

@h0494 什么意思?


by wind_kaka @ 2023-05-13 19:51:04

@6371 我都跟你说了 ST 表只是 RMQ 问题的一种解法......

这道题是 RMQ 问题但是只能用线段树那些做

内存限制 125.00MB


by wind_kaka @ 2023-05-13 19:51:46

@6371 RMQ (大概)是指区间最值问题,ST 表只是其中一个解法


by wind_kaka @ 2023-05-13 19:52:17

@6371 解决办法:口糊线段树(((

我记得线段树是可以过的(


by Leonid @ 2023-05-13 19:53:22

@6371 内存限制卡掉了 st 表的做法。


| 下一页