caioj 1172 poj 2823 单调队列过渡题

给定一个n个数的数列，从左至右输出每个长度为m的数列段内的最大数。

输入：第一行两个整数n和m( 1<= n <= 20 0000,m<=n）。下来给出n个整数。
输出：一行一个整数，表示每连续m个数的最大值。
样例输入：
8 3
1 3 -1 -3 5 3 6 7
样例输出：
3
3
5
5
6
7

维护一个单调队列，列内严格递减。若是首端元素已经脱离当前M个元素的区间，则去除。若是新元素比队尾元素严格小，直接入队，否则元素出队至合格后，新元素入队。比较模板了：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pii pair<int,int>

#define rep(i,a,b) for(int i=(a);i<(b);++i)

#define pb push_back

#define fi first

#define se second

const double eps=1e-, PI=acos(-1.0f);

const int inf=0x3f3f3f3f;

const int maxN=2e5+;

int N, M, K, T;

int g[maxN];

deque<pii> dq;

int main() {

#ifndef ONLINE_JUDGE

    freopen("data.in", "r", stdin);

#endif

    scanf("%d%d", &N, &M);

    for (int i = ; i <= N; ++i)

        scanf("%d", &g[i]);

    for (int i = ; i <= N; ++i) {

        while (dq.size() && dq.back().fi <= g[i])

            dq.pop_back();

        dq.push_back(pii(g[i], i));

        while (dq.back().se - dq.front().se +  > M)

            dq.pop_front();

        if (i >= M)

            printf("%d\n", dq.front().fi);

    }

    return ;

}

poj 2823 Sliding Window

用数组实现deque，得交c++，G++会TLE

#include <stdio.h>

#define FOR(i,a,b) for(int i=(a);i<=(b);++i)

#define maxN 1000005

int n, k, t, ab[maxN], as[maxN];

int lb, rb, ls, rs;

struct node{int v, i;} a, B[maxN], S[maxN];

int main () {

  //freopen("data.in", "r", stdin);

  scanf("%d%d", &n, &k);

  lb = rb = ls = rs = ;

  FOR(i, , n) {

    scanf("%d", &a.v), a.i = i;

    while (ls < rs && S[rs - ].v >= a.v) rs--;

    S[rs++] = a;

    if (S[ls].i <= i - k) ++ls;

    if (i >= k) ab[i] = S[ls].v;

    while (lb < rb && B[rb - ].v <= a.v) rb--;

    B[rb++] = a;

    if (B[lb].i <= i - k) ++lb;

    if (i >= k) as[i] = B[lb].v;

  }

  FOR(i, k, n) printf(i == k ? "" : " "), printf("%d", ab[i]);

  puts("");

  FOR(i, k, n) printf(i == k ? "" : " "), printf("%d", as[i]);

  return ;

}

巴特西

caioj 1172 poj 2823 单调队列过渡题

最新文章

热门文章