洛谷題目鏈接:[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

總結

以上是生活随笔為你收集整理的[HAOI2007] 理想的正方形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。