求助,有两个测试数据显示MLE,应该怎么修改?

P1440 求m区间内的最小值

Climb1104 @ 2024-03-09 08:27:25

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 2e6 + 10;
int f[N][22];
int n, m;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int min_l_r(int l, int r)
{
    int k = log2(r - l + 1);

    return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        f[i][0] = read();
    // 初始化ST表
    for (int j = 1; j <= 21; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
            printf("0\n");
        else if (i - 1 <= m)
        {
            printf("%d\n", min_l_r(1, i - 1));
        }
        else
        {
            printf("%d\n", min_l_r(i - m, i - 1));
        }
    }
    return 0;
}

by CC__DIAMOND @ 2024-03-27 17:47:45

这题很坑。虽然标签里有个RMQ,但是正常的ST会被卡内存。要过只有用单调队列。\ 可以看看P1886滑动窗口。这两题完全一样。


by Climb1104 @ 2024-03-30 17:44:28

@CC__DIAMOND 好的,谢谢


by CC__DIAMOND @ 2024-03-30 18:03:11

@Climb1104 好像这种RMQ做个滚动数组也能过?我后来在讨论区里看见一个,但是不太确定。


by Climb1104 @ 2024-03-31 08:13:24

@CC__DIAMOND 谢谢,我试一试


|