[原创]SPOJ MINSUN Largest Submatrix [二分+单调栈]

Tabris

CSDN杂类SPOJ

发布于：2017年1月8日

次浏览

[原创]SPOJ MINSUN Largest Submatrix [二分 + 单调栈]

2017-01-08 15:18:59 Tabris_ 阅读数：268

博客爬取于 2020-06-14 22:42:25
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54234049

题目链接：http://www.spoj.com/problems/MINSUB/
---------------------------------------------------------------------------------------.
MINSUB - Largest Submatrix
no tags
You are given an matrix M (consisting of nonnegative integers) and an integer K. For any submatrix of M' of M define min(M') to be the minimum value of all the entries of M'. Now your task is simple: find the maximum value of min(M') where M' is a submatrix of M of area at least K (where the area of a submatrix is equal to the number of rows times the number of columns it has).

Input

The first line contains a single integer T (T ≤ 10) denoting the number of test cases, T test cases follow. Each test case starts with a line containing three integers, R (R ≤ 1000), C (C ≤ 1000) and K (K ≤ R * C) which represent the number of rows, columns of the matrix and the parameter K. Then follow R lines each containing C nonnegative integers, representing the elements of the matrix M. Each element of M is ≤ 10^9

Output

For each test case output two integers: the maximum value of min(M'), where M' is a submatrix of M of area at least K, and the maximum area of a submatrix which attains the maximum value of min(M'). Output a single space between the two integers.

Example

Input:
2
2 2 2
1 1
1 1
3 3 2
1 2 3
4 5 6
7 8 9

Output:
1 4
8 2
------------------------------------------------------------------------------------------.

题目大意：问你找到一个面积大于 K 的子矩阵中的最小值，在保证最小值最大的情况下计算面积的最大值

解题思路：
首先最小值最大这种就想到了二分，甚至都想到了每次将>=mid的值用一表示，其他用 0 表示，然后枚举子矩阵的左上角和右下角二维树状数组计算值，这样的话总复杂度就到了O(n^4*log_2^3 n)
然后就不会了
看了 wannaflyunion 的题解才知道用一个叫做单调栈的东西能在O(nm)的复杂度中解决求子矩阵的最大值
想法也同样是每次将>=mid的值用一表示，其他用 0 表示。增加的是在这个过程中处理了每个点向左的 1 的个数，然后通过维护每一列的时候向上有几个不小于这个值的向下有几个不小于这个值的。 这个过程通过单调栈能做到O(n) ，然后判断的是m列的 所以总复杂度最后只到了O(nmlog_2(1e9+1))

因为二分的不同写法 注意下 1e9 这个值就好了，,,,

附本题代码
-----------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

再次抄袭wannaflyunion的代码..
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
void fre()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
/*************************************************/

int n,m,k;
int a[1005][1005],f[1005][1005],U[1005],D[1005];

int check(int x){
    memset(f,0,sizeof(f));
    memset(U,0,sizeof(U));
    memset(D,0,sizeof(D));

    Rep(i,1,n)Rep(j,1,m)
    if(a[i][j]>=x)f[i][j]=f[i][j-1]+1;
    else f[i][j]=0;

    int now ,area = 0;
    Rep(i,1,m){
        Rep(j,1,n){
            now = j-1;
            while(now&&f[j][i]<=f[now][i]) now = U[now];
            U[j] = now ;
        }
        Per(j,n,1){
            now = j+1;
            while(now!=n+1&&f[j][i]<=f[now][i]) now = D[now];
            D[j] = now;
        }
        Rep(j,1,n) area = max(area,(D[j]-U[j]-1)*f[j][i]);
    }
    return area;
}

int main()
{
    int _;
    while(~s1(_)){
        while(_--){
            s1(n),s1(m),s1(k);
            Rep(i,1,n)Rep(j,1,m) s1(a[i][j]);

            int l,r = -1,mid,ans;
            l = 0,r = 1e9+1,ans =0;
            while(l<=r){
                mid = (l+r)>>1;
                if(check(mid)>=k)    ans = mid, l=mid+1;
                else    r=mid-1;
            }
            printf("%d %d\n",ans,check(ans));
        }
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN