MLE求助

P1440 求m区间内的最小值

WydnksqhbD @ 2024-01-04 15:49:30

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+10;
int n,m;
int a[N],RMQ[N][21];
void ST()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&RMQ[i][0]);
    }
    for(int j=1;j<=(int)(log(n)/log(2));j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);
        }
    }
    return;
}
int ask(int l,int r)
{
    int x=(int)(log(r-l+1)/log(2));
    return min(RMQ[l][x],RMQ[r-(1<<x)+1][x]);
}
int main()
{
    scanf("%d %d",&n,&m);
    ST();
    printf("0\n");
    for(int i=2;i<=n;i++)
    {
        int left=i-m,right=i-1;
        if(left<1)
        {
            left=1;
        }
        printf("%lld\n",ask(left,right));
    }
    return 0;
}

by xiaoshumiao @ 2024-01-04 16:05:04

@WydnksqhbD 您好,此题正解是单调队列。MLE 的原因是 2 \times 10^6 \times 21 的数组 要约 160MB 的内存。


by WydnksqhbD @ 2024-01-04 16:09:22

@xiaoshumiao 如果我不会单调队列怎么办。。。


by xiaoshumiao @ 2024-01-04 16:10:33

@WydnksqhbD 学。


by WydnksqhbD @ 2024-01-04 16:10:56

@xiaoshumiao 6


|