第十三届蓝桥杯JavaB组省赛F题——最大子矩阵 (AC)

迷南。 2023-09-28 23:11 49阅读 0赞

#### 目录 ####

*  1.最大子矩阵
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.Ac\_code

## 1.最大子矩阵 ##

### 1.问题描述 ###

小明有一个大小为  N × M N × M N×M 的矩阵，可以理解为一个  N N N 行  M M M 列的二维数组。我们定义一个矩阵  m m m 的稳定度  f ( m ) f(m) f(m) 为  f ( m ) = m a x ( m ) − m i n ( m ) f(m) = max(m) − min(m) f(m)=max(m)−min(m)，其中  m a x ( m ) max(m) max(m)  
表示矩阵  m m m 中的最大值， m i n ( m ) min(m) min(m) 表示矩阵  m m m 中的最小值。现在小明想要从这个矩阵中找到一个稳定度**不大于**  l i m i t limit limit 的子矩阵，同时他还希望这个子矩阵的面积越大越好（面积可以理解为矩阵中元素个数）。  
子矩阵定义如下：从原矩阵中选择一组连续的行和一组连续的列，这些行列交点上的元素组成的矩阵即为一个子矩阵。

### 2.输入格式 ###

第一行输入两个整数  N ， M N，M N，M，表示矩阵的大小。  
  接下来  N N N 行，每行输入  M M M 个整数，表示这个矩阵。  
  最后一行输入一个整数  l i m i t limit limit，表示限制。

### 3.输出格式 ###

输出一个整数，分别表示小明选择的子矩阵的**最大**面积。

### 4.样例输入 ###

3 4  
**2 0** 7 9  
**0 6** 9 7  
**8 4** 6 4  
8

### 5.样例输出 ###

### 6.数据范围 ###

1 ≤ n ≤ 80 ， 1 ≤ m ≤ 1 0 5 ， 1 ≤ n ∗ m ≤ 1 0 5 1\\leq n \\leq80，1 \\leq m \\leq10^5，1 \\leq n\*m \\leq10^5 1≤n≤80，1≤m≤105，1≤n∗m≤105  
 0 ≤ 0 \\leq 0≤ 矩阵元素值， l i m i t ≤ 1 0 5 limit \\leq 10^5 limit≤105

### 7.原题链接 ###

[最大子矩阵][Link 1]

## 2.解题思路 ##

*   ( 1 ) (1) (1)题意比较简单，确定一个矩阵，只需要确定左上端点和右下端点，自然而然想到一个最朴素最暴力想法——去枚举两个端点。很显然这样的复杂度是 O ( n 2 m 2 β ( t ) ) O(n^2m^2 \\beta(t)) O(n2m2β(t))，其中 β ( t ) \\beta(t) β(t)是判断每个矩阵所需要的时间，设该矩阵的长为  x x x，宽为  y y y ，则 β ( t ) = x ∗ y \\beta(t)=x\*y β(t)=x∗y。但很明显这样的思路是超时的，光是  m 2 m^2 m2 的复杂度就是我们无法接受的。
 *   ( 2 ) (2) (2)假设一个矩阵的左上端点的坐标为 ( x 1 , y 1 ) (x\_1,y\_1) (x1,y1)，右下坐标的端点为 ( x 2 ， y 2 ) (x\_2，y\_2) (x2，y2)。仔细观察数据范围可以发现， n n n 非常小，这意味着我们可以暴力枚举两点的横坐标  x 1 x\_1 x1 和  x 2 x\_2 x2，这样做的复杂度为  n 2 n^2 n2。这样处理后，意味着我们只需要在这个下图中的红轴和橙轴各找到一个点，也就是找到  y 1 y1 y1 和  y 2 y2 y2 ,使得矩阵的稳定度是不大于 l i m i t limit limit，我们先不考虑如何枚举 y 1 y1 y1和 y 2 y2 y2这个问题，先考虑对于一个确定的矩阵，如何高效的算出它的 β ( t ) \\beta(t) β(t)。  
    ![在这里插入图片描述][48b18a873a2a4dd6be9c7aca8fc8fde3.png]
 *   ( 3 ) (3) (3)对于一个矩阵，并没有一个高效求出它的  m a x max max以及  m i n min min的算法 ,但如果是一个一维数组，求区间的最值就有许多方法，比如 s t st st表，线段树、单调队列等。我们不禁去思考，**能否将一个二维矩阵处理为一维？**  
    显然这是可行的！  
    假设对于一个下面的二维矩阵，设宽为  y y y，高为  x x x ，暴力求最值的复杂度是 O ( x y ) O(xy) O(xy)  
    ![在这里插入图片描述][8b5517378ce745b39954a667326d84e0.png]  
    如果我们可以先处理得到每一列的最值，并将其放到该列的末尾，那么对于该矩阵的最值，我们只需要考虑最后一行即可。![在这里插入图片描述][bc7d6f47f8f9469e8a2218ae0a939f61.png]  
    如图每个红色都格子都是该列的最值 ( m a x / m i n ) (max/min) (max/min)，那么当我们需要求解该矩阵的最大值或者最小值时，复杂度都将只和矩阵的宽度有关，时间复杂度将会是 O ( y ) O(y) O(y)。  
     ( 4 ) (4) (4)当然如何预处理是一个关键，我们生成两个数组 m a x \[ k \] \[ i \] \[ j \] max\[k\]\[i\]\[j\] max\[k\]\[i\]\[j\]以及 m i n \[ k \] \[ i \] \[ j \] min\[k\]\[i\]\[j\] min\[k\]\[i\]\[j\]，其中 m a x \[ k \] \[ i \] \[ j \] max\[k\]\[i\]\[j\] max\[k\]\[i\]\[j\]代表的含义是在第 k k k列中，第  i i i 个元素到第  j j j 个的元素最大值是多少， m i n min min数组同理。我们预处理的转移式子应该为：  
     m a x \[ k \] \[ i \] \[ j \] = m a x ( m a x \[ k \] \[ i \] \[ j − 1 \] , m a x \[ k \] \[ j \] \[ j \] ) ; max\[k\]\[i\]\[j\] =max(max\[k\]\[i\]\[j - 1\], max\[k\]\[j\]\[j\]); max\[k\]\[i\]\[j\]=max(max\[k\]\[i\]\[j−1\],max\[k\]\[j\]\[j\]);  
    这个式子的含义也很简单，对于区间 \[ i , j \] \[i,j\] \[i,j\]的最大值应该是 \[ i , j − 1 \] \[i,j-1\] \[i,j−1\]的最大值和  j j j 位值取较大值。  
    由于我们处理的是每一列，这样时间复杂度是 O ( n 2 ) O(n^2) O(n2)，由于总共有 m m m，所以总时间复杂度应该是 O ( n 2 m ) O(n^2m) O(n2m)，这是完全可接受的。这样我们就完成了这道题第一个难点的跨越。  
    **这一步的操作可以这样理解**：  
      有一个部落，它有 m m m个村庄，每次村庄都有 n n n个人，每次我们需要去找到一堆村庄内最强的那个人，如果每次计算最坏都有可能是 O ( n m ) O(nm) O(nm)的复杂度，那么不如先让每个村庄自己内部打一架，派出一个最强代表，每次我们只需要让代表打一架就好了，这样复杂度就只是 O ( m ) O(m) O(m)
 *   ( 5 ) (5) (5)现在让我们再回到之前的一个问题，确定了 x 1 x1 x1和 x 2 x2 x2的情况下，如何去确定 y 1 y1 y1和 y 2 y2 y2呢，如果同样暴力枚举的话复杂度是 O ( m 2 ) O(m^2) O(m2)不可接受。在这里我们可以巧妙地进行**二分答案**。因为本质上横坐标 x x x确定的是矩阵高，而 y y y确定的是矩阵的宽，我们去二分宽度——矩阵内是否存在宽度为  l l l 的矩阵稳定度不大于 l i m i t limit limit。
 *   ( 6 ) (6) (6)既然可以二分，那就一定要分析其是否具有二段性，明显是有的。如果存在一个宽度为  l l l 的矩阵符合要求，那么一定能找到一个宽度在区间 \[ 1 , l − 1 \] \[1,l-1\] \[1,l−1\]的矩阵也符合要求。这也非常好证明：对于下图  
    ![在这里插入图片描述][a9db316891b1462fbb361db60d40b40f.png]  
    假设红色矩阵的值域为 \[ l , r \] \[l,r\] \[l,r\]，且 r − l < = l i m i t r-l<=limit r−l<=limit，说明该矩阵是稳定矩阵。因为橙色、蓝色、黄色矩阵都是红色的子矩阵，说明它的值域一定也是在 \[ l , r \] \[l,r\] \[l,r\]，那么说明它们也一定是稳定矩阵，到此可以说明二分的正确性。本题的第二个难点就此解决。
 *   ( 7 ) (7) (7)当然既然二分当然要说明  c h e c k check check 函数的逻辑，当二分的值为 m i d mid mid时，也就是需要去判断是否存在宽度为 m i d mid mid的矩阵符合要求，因为我们前面预处理已经将高度压缩为`1`，所以这其实就是一个一维数组滑动窗口求最值问题，属于是单调队列的模板使用，求出每个长度为 m i d mid mid的窗口的最大值 m a x max max和最小值 m i n min min，只要有一个窗口符合 m a x − m i n < = l i m i t max-min<=limit max−min<=limit我们都返回`true`，否则返回`false`。
 *   ( 8 ) (8) (8)当二分得到最长宽度为  r r r 时，该矩阵的面积就为 ( x 2 − x 1 + 1 ) ∗ r (x2-x1+1)\*r (x2−x1\+1)∗r，每次用一个全局变量更新答案。考虑时间复杂度——枚举横坐标为 O ( n 2 ) O(n^2) O(n2)，二分的复杂度为 O ( l o g m ) O(logm) O(logm)，每次 c h e c k check check判定的复杂度是 O ( m ) O(m) O(m)，所以整体时间复杂度为 O ( n 2 m l o g m ) O(n^2mlogm) O(n2mlogm)。

## 3.Ac\_code ##

**Java**

import java.io.*;
    import java.util.*;
    
    public class Main {
        
        //max[k][i][j]表示第k列中[i,j]之间的最大值
        static int[][][] max;
        static int[][][] min;
        static int n, m, limit,ans;
        static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        public static void main(String[] args) throws IOException {
        
            String[] s=br.readLine().split(" ");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            max=new int[m+1][n+1][n+1];
            min=new int[m+1][n+1][n+1];
            for (int i = 1; i <= n; i++) {
        
                s=br.readLine().split(" ");
                for (int j = 1; j <= m; j++) {
        
                    max[j][i][i] = min[j][i][i] = Integer.parseInt(s[j-1]);
                }
            }
            limit = Integer.parseInt(br.readLine());
            //预处理  复杂度 n^2*m
            for (int k = 1; k <= m; ++k) {
        
                for (int i = 1; i <= n; ++i) {
        
                    for (int j = i + 1; j <= n; ++j) {
        
                        max[k][i][j] = Math.max(max[k][i][j - 1], max[k][j][j]);
                        min[k][i][j] = Math.min(min[k][i][j - 1], min[k][j][j]);
                    }
                }
            }
            for (int x1 = 1; x1 <= n; x1++) {
        
                for (int x2 = x1; x2 <= n; x2++) {
        
                    int l = 1, r = m;
                    while (l < r) {
        
                        int mid = l + r + 1 >> 1;
                        if (check(x1, x2, mid)) l = mid;
                        else r = mid - 1;
                    }
                    if (check(x1,x2,r)) ans=Math.max(ans,(x2-x1+1)*r);
                }
            }
            out.println(ans);
            out.flush();
        }
    
        //k是窗口大小
        static boolean check(int x1, int x2, int k) {
        
            Deque<Integer> qmax = new ArrayDeque<>();
            Deque<Integer> qmin = new ArrayDeque<>();
            for (int i = 1; i <= m; i++) {
        
                //处理最小
                if (!qmin.isEmpty() && qmin.peekFirst() < i - k + 1) qmin.pollFirst();
                while (!qmin.isEmpty() && min[qmin.peekLast()][x1][x2] > min[i][x1][x2]) qmin.pollLast();
                qmin.offerLast(i);
                //处理最大
                if (!qmax.isEmpty() && qmax.peekFirst() < i - k + 1) qmax.pollFirst();
                while (!qmax.isEmpty() && max[qmax.peekLast()][x1][x2] < max[i][x1][x2]) qmax.pollLast();
                qmax.offerLast(i);
                //说明窗口为k
                if (i >= k && max[qmax.peekFirst()][x1][x2] - min[qmin.peekFirst()][x1][x2] <= limit) return true;
            }
            return false;
        }
    }

**C++**

#include <bits/stdc++.h>
    using namespace std;
    const int N = 81, M = 100010;
    int n, m, lim, ans;
    bool check(vector<vector<vector<int>>> &minv, vector<vector<vector<int>>> &maxv, int r1, int r2, int k) {
        
        deque<int> qmax, qmin;
        for (int i = 1; i <= m; ++i) {
        
            if (!qmin.empty() && i - qmin.front() + 1 > k) qmin.pop_front();
            while (!qmin.empty() && minv[qmin.back()][r1][r2] > minv[i][r1][r2]) qmin.pop_back();
            qmin.push_back(i);
            if (!qmax.empty() && i - qmax.front() + 1 > k) qmax.pop_front();
            while (!qmax.empty() && maxv[qmax.back()][r1][r2] < maxv[i][r1][r2]) qmax.pop_back();
            qmax.push_back(i);
            if (i >= k && maxv[qmax.front()][r1][r2] - minv[qmin.front()][r1][r2] <= lim) return true;
        }
        return false;
    }
    int main() {
        
        ios::sync_with_stdio(false); cin.tie(0);
        cin >> n >> m;
        vector<vector<vector<int>>> minv(m + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
        vector<vector<vector<int>>> maxv(m + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> minv[j][i][i], maxv[j][i][i] = minv[j][i][i];
        cin >> lim;
        for (int k = 1; k <= m; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = i + 1; j <= n; ++j) {
        
                    maxv[k][i][j] = max(maxv[k][i][j - 1], maxv[k][j][j]);
                    minv[k][i][j] = min(minv[k][i][j - 1], minv[k][j][j]);
                }
        for (int r1 = 1; r1 <= n; ++r1) {
        
            for (int r2 = r1; r2 <= n; ++r2) {
        
                int l = 0, r = m;
                while (l < r) {
        
                    int mid = l + r + 1 >> 1;
                    if (check(minv, maxv, r1, r2, mid)) l = mid;
                    else r = mid - 1;
                }
                ans = max(ans, (r2 - r1 + 1) * l);
            }
        }
        cout << ans;
    }

[Link 1]: https://www.lanqiao.cn/problems/2147/learning/
[48b18a873a2a4dd6be9c7aca8fc8fde3.png]: https://img-blog.csdnimg.cn/48b18a873a2a4dd6be9c7aca8fc8fde3.png
[8b5517378ce745b39954a667326d84e0.png]: https://img-blog.csdnimg.cn/8b5517378ce745b39954a667326d84e0.png
[bc7d6f47f8f9469e8a2218ae0a939f61.png]: https://img-blog.csdnimg.cn/bc7d6f47f8f9469e8a2218ae0a939f61.png
[a9db316891b1462fbb361db60d40b40f.png]: https://img-blog.csdnimg.cn/a9db316891b1462fbb361db60d40b40f.png