怎么可以卡内存呢

P1440 求m区间内的最小值

凑_友希那 @ 2018-04-18 22:25:34

#include <bits/stdc++.h>

using namespace std;

/**
* Code by mTx
* 题解: 砂糖表
* time: 2018/4/18
*/

///int st[22][2000001];
///short lg[2000001];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int tmp = ceil(log(n) / log(2));
    int **st = new int*[tmp + 1];
    for(int i = 0; i <= tmp; i++) {
        st[i] = new int[n + 1];
    }
    short *lg = new short[n + 1];
    lg[0] = lg[1] = 0;
    for(int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for(int i = 1; i <= n; i++)
        scanf("%d", &st[0][i]);
    for(int k = 0; k < tmp; k++)
        for(int i = 1; i <= n; i++)
            st[k + 1][i] = min(st[k][i], st[k][min(n, i + (1 << k))]);
    printf("0\n");
    for(int j = 1, i = 1; j < n; j++, i =max(1, j - m + 1)) {
        int t = int(lg[j - i + 1]);
        printf("%d\n", min(st[t][i], st[t][j - (1 << t) + 1]));
    }
    return 0;
}

by moongazer @ 2018-04-19 06:45:49

emmmmmmmmmmm,你可以试试单调队列 用ST表当然不行


by moongazer @ 2018-04-19 06:56:25

其实应该优化一下空间也可以


by moongazer @ 2018-04-19 06:56:51

题解中也有用ST表的


|