luogu 2216 理想的正方形

题目描述

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入格式

第一行为3个整数，分别表示a,b,n的值

第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式

仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例

输入 #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

分析

直接暴力O（a*b*n*n），想办法优化

我们发现正方形的边长固定，要在这个固定的区间中找最小值与最大值的最小差

固定区间，嗯，考虑考虑单调队列？

（虽说其他的数据结构也可以）

既然是二维的，怎么实现呢，单调队列可是线性的

这个好办，先处理行，再用行的结果处理列就好

怎么想到呢

我们分析自己的暴力程序，发现在处理最大最小值时做了很多无用功

这根线性的题分析是一样的

处理最大最小值有单调队列优化

先处理行：

根据行的结论处理列：

好啦

代码

  1 /***********************
  2 User：Mandy.H.Y
  3 Language:c++
  4 Problem:luogu 2216
  5 Algorithm:
  6 Date:2019.9.4 
  7 ***********************/
  8 
  9 #include<bits/stdc++.h>
 10 
 11 using namespace std;
 12 
 13 const int maxn = 1005;
 14 
 15 int n,m,l;
 16 int a[maxn][maxn];
 17 int l1,r1,l2,r2;
 18 int q1[maxn],q2[maxn];
 19 int mx1[maxn][maxn],mx2[maxn][maxn];
 20 int my1[maxn][maxn],my2[maxn][maxn];
 21 
 22 template<class T>inline void read(T &x){
 23     x = 0;bool flag = 0;char ch = getchar();
 24     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 25     while(isdigit(ch)) x = (x << 1) + (x <<3) + (ch ^ 48),ch = getchar();
 26     if(flag) x = -x;
 27 }
 28 
 29 template<class T>void putch(const T x){
 30     if(x > 9) putch(x / 10);
 31     putchar(x % 10 | 48);
 32 }
 33 
 34 template<class T>void put(const T x){
 35     if(x < 0) putchar('-'),putch(-x);
 36     else putch(x);
 37 }
 38 
 39 void file(){
 40     freopen("2216.in","r",stdin);
 41 //    freopen("2216.out","w",stdout);
 42 }
 43 
 44 void readdata(){
 45     read(n);read(m);read(l);
 46     for(int i = 1; i <= n; ++ i)
 47         for(int j = 1;j <= m; ++ j)
 48             read(a[i][j]);
 49 }
 50 
 51 void work(){
 52     //行 
 53     for(int i = 1;i <= n; ++ i){
 54         l1 = r1 = 0;
 55         l2 = r2 = 0;
 56         for(int j = 1;j <= m; ++ j){
 57             
 58             while(l1 < r1 && (q1[l1] <= j - l)) l1++;
 59             while(l2 < r2 && (q2[l2] <= j - l)) l2++;
 60             
 61             while(l1 < r1 && a[i][j] >= a[i][q1[r1 - 1]]) r1 --;
 62             while(l2 < r2 && a[i][j] <= a[i][q2[r2 - 1]]) r2 --;
 63             
 64             q1[r1 ++ ] = j;
 65             q2[r2 ++ ] = j;
 66             
 67             if(l1 < r1) mx1[i][j] = a[i][q1[l1]];//第i行j-l+1~j的最大值 
 68             if(l2 < r2) mx2[i][j] = a[i][q2[l2]];//第i行j-l+1~j的最小值 
 69             //这个放在队列更新后，因为包括自身 
 70             //注意要存值而不是编号
 71             //处理列的时候可以用到 
 72         }
 73     }
 74     //列 
 75     for(int i = 1;i <= m; ++ i){
 76         l1 = r1 = 0;
 77         l2 = r2 = 0;
 78         for(int j = 1;j <= n; ++ j){
 79             
 80             while(l1 < r1 && (q1[l1] <= j - l)) l1++;
 81             while(l2 < r2 && (q2[l2] <= j - l)) l2++;
 82             
 83             
 84             while(l1 < r1 && mx1[j][i] >= mx1[q1[r1 - 1]][i]) r1 --;
 85             while(l2 < r2 && mx2[j][i] <= mx2[q2[r2 - 1]][i]) r2 --;
 86             //直接用行的结果
 87             //可以直接处理出以(i,j)为右下角顶点的n*n的最大值与最小值 
 88             q1[r1 ++ ] = j;
 89             q2[r2 ++ ] = j;
 90             
 91             if(l1 < r1) my1[j][i] = mx1[q1[l1]][i];//最大值 
 92             if(l2 < r2) my2[j][i] = mx2[q2[l2]][i];//最小值 
 93             
 94         }
 95     }
 96     int ans = 2e9;
 97     for(int i = l;i <= n; ++ i)
 98         for(int j = l;j <= m; ++ j){
 99             ans = min(ans,my1[i][j] - my2[i][j]);
100         }
101     put(ans);
102 }
103 
104 int main(){
105 //    file();
106     readdata();
107     work();
108     return 0;
109 }

View Code