ST表解法求助,80分,2与10 RE

P1440 求m区间内的最小值

luokes @ 2023-03-25 15:18:11

代码如下

#include <bits/stdc++.h>

#define NMAX 1000000
using namespace std;

int n,m;
int st[NMAX+1][32];

int calc(int l,int r)
{
    int m = log2(r-l+1);
    return min(st[l][m],st[r-(1<<m)+1][m]);
}

int main()
{
    cin >> n >> m;
    // [1] 获取数据,并进行预处理
    for(int i = 1;i <= n;i++)
    {
        cin >> st[i][0];
    }
    for(int j = 1;(1<<j)-2 <= n;j++)
    {
        for(int i = 1;i+(1<<j)-1 <= n;i++)
        {
            st[i][j] = min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
    // [2] 查询
    cout << 0 << endl;
    for(int i = 2;i <= n;i++)
    {
        if(i <= m) printf("%d\n",calc(1,i-1));
        else printf("%d\n",calc(i-m,i-1));
    }
    return 0;
}      

by xs_siqi @ 2023-04-05 09:14:13

数组开小了


by Da_233 @ 2023-04-09 23:23:37

这题拿st表做会有两个点爆内存


|