Brief description:

。。维护一个宽度为 k 的滑动窗口。。分别统计所有位置的最大值和最小值。。

Analysis:

1. C++ 怎么都过。 / G++ 怎么都 TLE 。。
2. “那些500-600MS的代码到底是怎么弄出来的。。”。。
.. .

const int N = 1000009;

int a[N], q[N], cz, op;
int n, k;

template<class T> void gao(T cmp){

    cz = 0, op = -1; REP_1(i, k){
        while (cz <= op && cmp(a[i], a[q[op]])) --op;
        q[++op] = i;
    }

    printf("%d ", a[q[cz]]);

    FOR_1(i, k + 1, n){
        if (q[cz] == i - k) ++cz;
        while (cz <= op && cmp(a[i], a[q[op]])) --op;
        q[++op] = i; printf("%d ", a[q[cz]]);

    }

    puts("");
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, k); REP_1(i, n) RD(a[i]);
    gao(less<int>()), gao(greater<int>());
}

External link:

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=16694

Posted by xiaodao
Category: HDU
Tags: 单调队列