_(:з」∠)_各位菊苣,我自认为方法没问题也不会tle

P1886 滑动窗口 /【模板】单调队列

gaoy_vipcode @ 2019-05-17 20:23:13

只有1、3过了,其他全wa

#include <stdio.h>
#define MAX 1000050

int max[MAX];
int min[MAX];

int main(){
    int n, k, t;
    int a, b;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i){
        scanf("%d", &t);
        max[i] = min[i] = t;
    }
    // 处理
    for(int i = k - 1; i < n; ++i){
        a = b = i - 1;
        while( (max[a] < max[i]) && ((i - a) < k) ) max[a--] = max[i];
        while( (min[b] > min[i]) && ((i - b) < k) ) min[b--] = min[i];
    }
    //输出
    n = n - k + 1;
    printf("%d", min[0]);
    for(int i = 1; i < n; ++i)
        printf(" %d", min[i]);
    printf("\n");

    printf("%d", max[0]);
    for(int i = 1; i < n; ++i)
        printf(" %d", max[i]);

    return 0;
}

by aminoas @ 2019-05-17 20:24:02

Link Queue是个好东西


by NaCly_Fish @ 2019-05-17 21:01:54

这题大力线段树啊(


|