求优化

P1440 求m区间内的最小值

Ikari_Shinji @ 2019-01-18 21:51:24

50分,测评情况:

#include<cstdio>
#define min(a,b) (a<b?a:b)

const int N=2000005;
int n,m,a[N],ans[N];

int main(){

    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    ans[0]=0;
    ans[1]=a[0];
    for(int i=2;i<n;i++){
        int num=2147483647;
        for(int j=1;j<=m;j++){
            if(i-j<0) break;
            else num=min(num,a[i-j]);
        }
        ans[i]=num;
    }
    for(int i=0;i<n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

by SSerxhs @ 2019-01-18 21:53:03

复杂度都不对就洗洗睡吧


by 周子衡 @ 2019-01-18 21:54:50

单调队列题


by Kevin_Wa @ 2019-01-18 21:56:49

线段树


by 周子衡 @ 2019-01-18 22:00:48

暴力显然是O(nm)

我们可以构造一个队列,保存所有可能成为正确答案的元素

顺序扫描每一个元素,可以发现:如果i<ja_i\geq a_j,那么a_i在有生之年就肯定不是正确答案,就从队中踢出

每次如果最先进入队列的元素过期了,也把它踢出

可以发现,这个队列的元素单调递增,故称单调队列

我讲得可能不是很清楚,具体看题解和日报吧

可以用STLdeque


by 周子衡 @ 2019-01-18 22:01:15

时间复杂度O(n)


|