理想的正方形

LibreOJ-10182-理想的正方形

实现

#include <iostream>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 1010;
int n, m, k;
int a[N][N];
int ri[N][N], ra[N][N];
int x[N], y[N], z[N];

void get_min_val (int a[], int b[], int n) {
    deque<int> dq;
    for (int i = 1; i <= n; ++ i) {
        if (!dq.empty() && i - dq.front() + 1 > k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k) b[i] = a[dq.front()];
    }
}
void get_max_val (int a[], int b[], int n) {
    deque<int> dq;
    for (int i = 1; i <= n; ++ i) {
        if (!dq.empty() && i - dq.front() + 1 > k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k) b[i] = a[dq.front()];
    }
}

int main () {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; ++ i) {
        get_min_val(a[i], ri[i], m);
        get_max_val(a[i], ra[i], m);
    }
    int res = inf;
    for (int j = k; j <= m; ++ j) {
        for (int i = 1; i <= n; ++ i) x[i] = ri[i][j];
        get_min_val(x, y, n);

        for (int i = 1; i <= n; ++ i) x[i] = ra[i][j];
        get_max_val(x, z, n);

        for (int i = k; i <= n; ++ i) res = min(res, z[i] - y[i]);
    }
    printf("%d", res);
    return 0;
}