[HAOI2007] 理想的正方形

洛谷題目連結:[HAOI2007]理想的正方形

題目描述

有一個ab的整數組成的矩陣，現請你從中找出一個nn的正方形區域，使得該區域所有數中的最大值和最小值的差最小。

輸入輸出格式

輸入格式：

第一行為3個整數，分别表示a,b,n的值

第二行至第a+1行每行為b個非負整數，表示矩陣中相應位置上的數。每行相鄰兩數之間用一空格分隔。

輸出格式：

僅一個整數，為ab矩陣中所有“nn正方形區域中的最大整數和最小整數的內插補點”的最小值。

輸入輸出樣例

輸入樣例#1：

5 4 2

1 2 5 6

0 17 16 0

16 17 2 1

2 10 2 1

1 2 2 2

輸出樣例#1：

1

說明

問題規模

（1）矩陣中的所有數都不超過1,000,000,000

（2）20%的資料2<=a,b<=100,n<=a,n<=b,n<=10

（3）100%的資料2<=a,b<=1000,n<=a,n<=b,n<=100

一句話題意: 在一個\(n*m\)的矩陣中找一個大小為\(k\)的正方形使得這個正方形内的最大值與最小值的內插補點最小.

題解: 首先分析一下資料範圍,顯然這個算法的複雜度是\(O(n^2)\)的,然而這裡需要統計的是最值,無法使用字首和,是以這裡考慮使用單調隊列來維護.

既然是一個正方形,那麼很顯然在枚舉到這個正方形的左上角的頂點的時候,這個正方形就已經可以确定了.是以我們可以豎着先求一遍最大/最小值,然後再用這個最大/最小值來求出一個正方形中的最大/最小值.

這裡将每個位置向下\(k\)格的最大值/最小值用\(Mx[i][j]/Mn[i][j]\)存起來(即\(Mx[i][j] = max(a[i][j], a[i+1][j], ... , a[i+k-1][j])\), \(Mn[i][j]\)同理).

其實說白了就是先将每個位置求出連續的\(k\)個,也即是豎着求一遍滑動視窗,然後把這些連續的\(k\)個都看做一個個的格子,再橫着求一遍滑動視窗.這個可以好好想想為什麼.

#include<bits/stdc++.h>
using namespace std;
const int N=1000+5;
const int inf=2147483647;

int n, m, k, a[N][N], Mx[N][N], Mn[N][N], mx[N], mn[N], h1, t1, h2, t2, ans = inf;

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> a[i][j];
    
    for(int i=1; i<=m; i++){//豎着求最大值,儲存到Mx[i][j]/Mn[i][j]中
        h1 = h2 = 1, t1 = t2 = 0;
        for(int j=1; j<=n; j++){
            while(h1 <= t1 && a[mx[t1]][i] <= a[j][i]) t1--;
            while(h2 <= t2 && a[mn[t2]][i] >= a[j][i]) t2--;
            mx[++t1] = mn[++t2] = j;
            while(h1 <= t1 && mx[h1]+k <= mx[t1]) h1++;
            while(h2 <= t2 && mn[h2]+k <= mn[t2]) h2++;
            if(j >= k) Mx[j-k+1][i] = a[mx[h1]][i], Mn[j-k+1][i] = a[mn[h2]][i];
        }
    }
    
    for(int i=1; i<=n-k+1; i++){
        h1 = h2 = 1, t1 = t2 = 0, mx[t1] = mn[t2] = 0;
        for(int j=1; j<=m; j++){
            while(h1 <= t1 && Mx[i][mx[t1]] <= Mx[i][j]) t1--;
            while(h2 <= t2 && Mn[i][mn[t2]] >= Mn[i][j]) t2--;
            mx[++t1] = mn[++t2] = j;
            while(h1 <= t1 && mx[h1]+k <= mx[t1]) h1++;
            while(h2 <= t2 && mn[h2]+k <= mn[t2]) h2++;
            if(j >= k) ans = min(ans, Mx[i][mx[h1]]-Mn[i][mn[h2]]);
        }
    }
    
    printf("%d\n", ans);
    return 0;
}                

轉載于:https://www.cnblogs.com/BCOI/p/9166730.html