洛谷 P2216 [HAOI2007]理想的正方形
Description
- 有一个ab的整数组成的矩阵，现请你从中找出一个nn的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
Input
第一行为3个整数，分别表示a,b,n的值
第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
Output
- 仅一个整数，为ab矩阵中所有“nn正方形区域中的最大整数和最小整数的差值”的最小值。
Sample Input
5 4 21 2 5 60 17 16 016 17 2 12 10 2 11 2 2 2
Sample Output
1
题解：
- 单调队列。
- 一发A掉了，舒服。
- 对于求出一个n * n的矩形中的最大值，可以想成求出n行中每行最大值中的最大值。每行的最大值怎么求？线段树、ST表都OK。但是用单调队列岂不是更好？
- 所以先用单调队列求出以点(i, j)为第i行的j - n + 1 ~ j的格子中的最大/小值。
- 那么对于一个矩形我们只需要枚举n次就可以得到最大/小值了。
- 但是，你用纸笔画画n * n矩形框选的范围。可以发现每次矩形都是整体向下挪了一个格子。那么这又是一个单调队列呀。只不过这次单调队列中的元素是以点(i, j)为第i行的j - n + 1 ~ j的格子中的最大/小值。
- 复杂度大概是O(2ab) = O(n ^ 2的规模)。
- 哦，我偷懒用STL，常数巨大。不开O2 90pts，开了O2可以A。
#include#include #include #define N 1005#define inf 0x7fffffffusing namespace std;struct Node1{ int val, pos; friend bool operator < (Node1 x, Node1 y) { return x.val < y.val; }};struct Node2{ int val, pos; friend bool operator < (Node2 x, Node2 y) { return x.val > y.val; }};int n, m, len, ans = inf;int Max[N][N], Min[N][N];int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}int main(){ cin >> n >> m >> len; for(int i = 1; i <= n; i++) { priority_queue que1; priority_queue que2; for(int j = 1; j < len; j++) { int x = read(); que1.push((Node1){x, j}); que2.push((Node2){x, j}); } for(int j = len; j <= m; j++) { while(que1.size() && que1.top().pos <= j - len) que1.pop(); while(que2.size() && que2.top().pos <= j - len) que2.pop(); int x = read(); que1.push((Node1){x, j}); que2.push((Node2){x, j}); Max[i][j] = que1.top().val; Min[i][j] = que2.top().val; } } for(int j = len; j <= m; j++) { priority_queue que1; priority_queue que2; for(int i = 1; i < len; i++) { int v1 = Max[i][j]; int v2 = Min[i][j]; que1.push((Node1){v1, i}); que2.push((Node2){v2, i}); } for(int i = len; i <= n; i++) { while(que1.size() && que1.top().pos <= i - len) que1.pop(); while(que2.size() && que2.top().pos <= i - len) que2.pop(); int v1 = Max[i][j]; int v2 = Min[i][j]; que1.push((Node1){v1, i}); que2.push((Node2){v2, i}); ans = min(ans, que1.top().val - que2.top().val); } } cout << ans; return 0;}