题目链接: P2216 [HAOI2007] 理想的正方形 https://www.luogu.org/problem/P2216
题目描述
有一个 \(a\times b\) 的整数组成的矩阵, 现请你从中找出一个 \(n\times n\) 的正方形区域, 使得该区域所有数中的最大值和最小值的差最小.
输入格式
第一行为 3 个整数, 分别表示 a,b,n 的值
第二行至第 a+1 行每行为 b 个非负整数, 表示矩阵中相应位置上的数. 每行相邻两数之间用一空格分隔.
输出格式
仅一个整数, 为 \(a\times b\) 矩阵中所有 "\(n\times n\) 正方形区域中的最大整数和最小整数的差值" 的最小值.
输入输出样例
输入 #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
思路
单调队列
二维 RMQ 问题.
设原矩阵为 m[][], 用单调队列求每行的最大 / 最小值, 分别存入两个矩阵 maxr[][] 和 minr[][].maxr[i][j] 代表 m[i][j] 到 m[i][j + n - 1] 的最大值, minr[i][j] 代表 m[i][j] 到 m[i][j + n - 1] 的最小值.
接下来对这两个矩阵用单调队列求每列的最大 / 最小值, 分别存入两个矩阵 maxc[][] 和 minc[][].maxr[i][j] 代表 m[i][j] 到 m[i + n - 1][j + n - 1] 的最大值, minr[i][j] 代表 m[i][j] 到 m[i + n - 1][j + n - 1] 的最小值.
最后遍历 maxc[][] 和 minc[][] 即可.
代码
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1010;
- const int inf = 0x3f3f3f3f;
- int m[maxn][maxn];
- int maxr[maxn][maxn], maxc[maxn][maxn];
- int minr[maxn][maxn], minc[maxn][maxn];
- int main() {
- iOS::sync_with_stdio(false);
- cin.tie(0);
- int a, b, n;
- cin>> a>> b>> n;
- for(int i = 1; i <= a; ++i) {
- for(int j = 1; j <= b; ++j) {
- cin>> m[i][j];
- }
- }
- for(int i = 1; i <= a; ++i) {
- int l = 1, r = 1;
- int L = 1, R = 1;
- int q1[maxn] = {0, l}, q2[maxn] = {0, L};
- for(int j = 2; j <= b; ++j) {
- while(r>= l && j - q1[l]>= n) ++l;
- while(r>= l && m[i][j] <= m[i][q1[r]]) --r;
- q1[++r] = j;
- if(j>= n) minr[i][j - n + 1] = m[i][q1[l]];
- while(R>= L && j - q2[L]>= n) ++L;
- while(R>= L && m[i][j]>= m[i][q2[R]]) --R;
- q2[++R] = j;
- if(j>= n) maxr[i][j - n + 1] = m[i][q2[L]];
- }
- }
- for(int i = 1; i <= b - n + 1; ++i) {
- int l = 1, r = 1;
- int L = 1, R = 1;
- int q1[maxn] = {0, l}, q2[maxn] = {0, L};
- for(int j = 2; j <= a; ++j) {
- while(r>= l && j - q1[l]>= n) ++l;
- while(r>= l && minr[j][i] <= minr[q1[r]][i]) --r;
- q1[++r] = j;
- if(j>= n) minc[j - n + 1][i] = minr[q1[l]][i];
- while(R>= L && j - q2[L]>= n) ++L;
- while(R>= L && maxr[j][i]>= maxr[q2[R]][i]) --R;
- q2[++R] = j;
- if(j>= n) maxc[j - n + 1][i] = maxr[q2[L]][i];
- }
- }
- int ans = inf;
- for(int i = 1; i <= a - n + 1; ++i) {
- for(int j = 1; j <= b - n + 1; ++j) {
- ans = min(ans, maxc[i][j] - minc[i][j]);
- }
- }
- cout << ans << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3190337.html