P9905 [COCI 2023/2024 #1] AN2DL 题解

Little_x_starTYJ · 2024-02-28 17:08:19 · 题解

解题思路

这道题目我们一看，咦？怎么有点像滑动窗口呢？于是就想到了单调队列。

我们定义一个单调队列，对于每一个数，我们判断队头的数字是否小于等于当前数，如果是，那么当前数一定更优，因为他不仅可以在队列里多待一会且贡献大于等于队头，所以我们循环弹出队头，直到队头大于当前数，然后入队清除过时的元素即可。

由于是二维的，所以需要跑两遍。

CODE：

#include <stdio.h>
#include <string.h>
int a[4001][4001], ans[4001][4001], b[4001][4001], q[2];
inline int read() {
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}
inline void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int main() {
    int n = read(), m = read();
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            a[i][j] = read();
    int r = read(), s = read();
    int k = n - r + 1, k2 = m - s + 1;
    for (i = 1; i <= n; i++) {
        int hh = 0, tt = -1;
        for (j = 1; j <= m; j++) {
            while (hh <= tt && a[i][q[tt]] <= a[i][j])
                tt--;
            q[++tt] = j;
            while (hh <= tt && q[hh] <= j - s)
                hh++;
            if (j >= s)
                b[i][j - s + 1] = a[i][q[hh]];
        }
        memset(q, 0, sizeof(q));
    }
    for (j = 1; j <= k2; j++) {
        int hh = 0, tt = -1;
        for (i = 1; i <= n; i++) {
            while (hh <= tt && b[q[tt]][j] <= b[i][j])
                tt--;
            q[++tt] = i;
            while (hh <= tt && q[hh] <= i - r)
                hh++;
            if (i >= r)
                ans[i - r + 1][j] = b[q[hh]][j];
        }
        memset(q, 0, sizeof(q));
    }
    for (i = 1; i <= k; i++, puts(""))
        for (j = 1; j <= k2; j++)
            write(ans[i][j]), putchar(' ');
    return 0;
}